排序綜合實驗

實驗名稱：排序綜合實驗實驗?zāi)康模簠⒄崭鞣N排序算法程序樣例，驗證給出的排序常見算法。實驗內(nèi)容：輸入一組關(guān)鍵字序列分別實現(xiàn)下列排序:實現(xiàn)簡單選擇排序、直接插入排序和冒泡排序。實現(xiàn)希爾排序算法。實現(xiàn)快速排序算法（取第一個記錄或中間記錄作為基準記錄）?？焖倥判虻姆沁f歸算法。實驗要求：掌握各種排序算法的特點，測試并驗證排序的常見算法。提交實驗報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。實驗原理直接插入排序：在線性表中只包含第一個元素的子表顯然可以看成是有序表，接下來的問題是，從線性表的第二個元素開始直到最后一個元素，逐次將其中的每一個元素插入到前面已經(jīng)有序的子表中。一般來說，假設(shè)線性表中前j-1個元素已經(jīng)有序，將第j個元素插入到前面的有序子表的方法是：首先將第j個元素放到一個變量T中，然后從有序子表的最后一個元素開始逐個與T比較，將大于T的元素均依次向后移動一個位置，直到發(fā)現(xiàn)一個元素不大于T為止，此時就將T插入到剛移出的空位置上，有序子表的長度就變?yōu)閖了。冒泡排序：首先從表頭開始往后掃描線性表，在掃描過程中逐次比較兩個相鄰元素的大小，若前面的元素大于后面的則互換，，最后將最大的元素移到了最后，然后從后到前掃描剩下的線性表，同樣掃描過程中逐次比較相鄰兩個元素的大小，若后面的元素小于前面的，則互換，最后將最小的元素移到了最前面，對剩下的線性表重復(fù)上面的過程，直到剩下的表為空，線性表有序?？焖倥判颍簭木€性表中選取一個元素T,然后將線性表后面小于T的元素移到前面，而大于T的元素移到后面，結(jié)果就將線性表分成了兩部分（稱為兩個字表），T插入到分界線的位置處，如果對分割后的各子表再按上述原則將進行分割，直到所有子表為空為止，線性表有序。堆排序：首先將一個無序序列建成堆，然后將堆頂元素(序列中的最大項)與堆中最后一個元素交換，不考慮已經(jīng)換到最后的那個元素，只考慮前n-1個元素構(gòu)成的子序列，顯然該序列已不是堆，但左右子樹仍為堆，可以將該子序列調(diào)整為堆，重復(fù)操作，直到剩下的子序列為空為止。實驗步驟：通過主函數(shù)選擇控制分別采用直接插入排序法、冒泡排序法、快速排序算法、快速排序的非遞歸算法、堆排序法實現(xiàn)給該組數(shù)據(jù)排序。實驗結(jié)果：#include<iostream>#include<iomanip>usingnamespacestd;//冒泡排序template<classT>voidbub(Tp[],intn){intm,k,j,i;Td;k=0;m=n-1;while(k<m){j=m-1;m=0;for(i=k;i<=j;i++)if(p[i]>p[i+1]){d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;}j=k+1;k=0;for(i=m;i>=j;i--)if(p[i-1]>p[i]){d=p[i];p[i]=p[i-1];p[i-1]=d;k=i;}}return;}//快速排序template<classT>voidqck(Tp[],intn)intm,i;T*s;if(n>10){i=split(p,n);qck(p,i);s=p+(i+1);m=n-(i+1);qck(s,m);}elsebub(p,n);return;}//表的分割template<classT>staticintsplit(Tp[],intn){inti,j,k,l;Tt;i=0;j=n-1;k=(i+j)/2;if((p[i]>=p[j])&&(p[j]>=p[k]))l=k;elseif((p[i]>=p[k])&&(p[k]>=p[j]))l=k;elsel=i;t=p[l];p[l]=p[i];while(i!=j){while((i<j)&&(p[j]>=t))j=j-1;if(i<j){p[i]=p[j];i=i+1;while((i<j)&&(p[i]<=t))i=i+1;if(i<j){p[j]=p[i];j=j-1;}}}p[i]=t;return(i);}//插入排序template<classT>voidinsort(Tp[],intn){intj,k;Tt;for(j=1;j<n;j++){t=p[j];k=j-1;while((k>=0)&&(p[k]>t)){p[k+1]=p[k];k=k-1;}p[k+1]=t;}return;}//希爾排序template<classT>voidshel(Tp[],intn){inti,k,j;Tt;k=n/2;while(k>0){for(j=k;j<=n-1;j++){t=p[j];i=j-k;while((i>=0)&&(p[i]>t)){p[j+k]=p[i];i=i-k;}p[i+k]=t;}k=k/2;}return;}//選擇排序template<classT>voidselect(Tp[],intn){inti,j,k;Td;for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(p[j]<p[k])k=j;if(k!=j){d=p[i];p[i]=p[k];p[k]=d;}}return;}template<classT>voidhap(Tp[],intn){inti,mm;Tt;mm=n/2;for(i=mm-1;i>=0;i--)sift(p,i,n-1);for(i=n-1;i>=1;i--){t=p[0];p[0]=p[i];p[i]=t;sift(p,0,i-1);}return;}intmain(){inti,j;doublep1[10]={4,3,2,1,5,7,6,8,9,0};doublep2[10]={4,3,2,1,5,7,6,8,9,0};doublep3[10]={4,3,2,1,5,7,6,8,9,0};doublep4[10]={4,3,2,1,5,7,6,8,9,0};doublep5[10]={4,3,2,1,5,7,6,8,9,0};cout<<"冒泡排序前的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p1[10*i+j];cout<<endl;}bub(p1,10);cout<<"冒泡排序后的序列："<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p1[10*i+j];cout<<endl;}cout<<"快速排序前的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p2[10*i+j];cout<<endl;}qck(p2,10);cout<<"快速排序后的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p2[10*i+j];cout<<endl;}cout<<"插入排序前的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p3[10*i+j];cout<<endl;}insort(p3,10);cout<<"插入排序后的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p3[10*i+j];cout<<endl;}cout<<"希爾排序前的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p4[10*i+j];cout<<endl;}shel(p4,10);cout<<"希爾排序后的序列:"<<endl;for(i=0;i<1;i++){for(j=0;j<10;j++)cout<<setw(5)<<p4[10*i+j];cout<<endl;}cout<<"選擇排序前的序列:"<<endl;for(i=0;i<1;i++){for(j=0