排序實驗報告

實驗五排序實驗目的:掌握幾種排序的思想及算法問題分析：(一)直接插入排序1.排序思想將待排序的記錄Ri，插入到已排好序的記錄表R1,R2,….,Ri-1中，得到一個新的、記錄數(shù)增加1的有序表。直到所有的記錄都插入完為止。設待排序的記錄順序存放在數(shù)組R[1…n]中，在排序的某一時刻，將記錄序列分成兩部分：◆R[1…i-1]：已排好序的有序部分；◆R[i…n]：未排好序的無序部分。顯然，在剛開始排序時，R[1]是已經排好序的。2.算法實現(xiàn)voidstraight_insert_sort(SqlistR){inti,j;for(i=2;i<=n;i++){R[0]=R[i];j=i-1;/*設置哨兵*/while(LT(R[0].key,R[j].key)){R[j+1]=R[j];j--;}/*查找插入位置*/R[j+1]=R[0];/*插入到相應位置*/}}（二）希爾排序1.排序思想①先取一個正整數(shù)d1(d1<n)作為第一個增量，將全部n個記錄分成d1組，把所有相隔d1的記錄放在一組中，即對于每個k(k=1,2,…d1)，R[k],R[d1+k],R[2d1+k],…分在同一組中，在各組內進行直接插入排序。這樣一次分組和排序過程稱為一趟希爾排序；②取新的增量d2<d1，重復①的分組和排序操作；直至所取的增量di=1為止，即所有記錄放進一個組中排序為止。2.算法實現(xiàn)先給出一趟希爾排序的算法，類似直接插入排序。voidshell_pass(SqlistR,intd)/*對順序表L進行一趟希爾排序,增量為d*/{intj,k;for(j=d+1;j<=n;j++){R[0]=R[j];/*設置監(jiān)視哨兵*/k=j-d;while(k>0&<(R[0].key,R[k].key)){R[k+d]=R[k];k=k-d;}R[k+d]=R[0];}}然后在根據(jù)增量數(shù)組dk進行希爾排序。voidshell_sort(SqlistR,intdk[],intt)/*按增量序列dk[0…t-1],對順序表L進行希爾排序*/{intm;for(m=0;m<t;m++)shll_pass(R,dk[m]);}增量序列取法◆無除1以外的公因子；◆最后一個增量值必須為1。（三）簡單選擇排序1.排序思想基本操作是：通過n-i次關鍵字間的比較，從n-i+1個記錄中選取關鍵字最小的記錄，然后和第i個記錄進行交換，i=1,2,…n-1。2.算法實現(xiàn)voidsimple_selection_sort(SqlistR){inti,j,k;for(i=1;i<n;i++){k=i;for(j=i+1;j<=n;j++)if(LT(R[j].key,R[k].key))k=j;if(k!=i)/*記錄交換*/{R[0]=R[k];R[k]=R[i];R[i]=R[0];}}}（四）堆排序1.排序思想①對一組待排序的記錄，按堆的定義建立堆；②將堆頂記錄和最后一個記錄交換位置，則前n-1個記錄是無序的，而最后一個記錄是有序的；③堆頂記錄被交換后，前n-1個記錄不再是堆，需將前n-1個待排序記錄重新組織成為一個堆，然后將堆頂記錄和倒數(shù)第二個記錄交換位置，即將整個序列中次小關鍵字值的記錄調整(排除)出無序區(qū)；④重復上述步驟，直到全部記錄排好序為止。排序過程中，若采用小根堆，排序后得到的是遞減序列；若采用大根堆，排序后得到的是遞增序列。堆的調整——篩選⑴堆的調整思想輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結點值與左、右子樹的根結點值進行比較，并與其中小者進行交換；重復上述操作，直到是葉子結點或其關鍵字值小于等于左、右子樹的關鍵字的值，將得到新的堆。稱這個從堆頂至葉子的調整過程為“篩選”，如圖10-10所示。⑵堆調整算法實現(xiàn)voidHeap_adjust(SqlistR,intlow,inthigh)/*R[low..high]中記錄關鍵字除R[low].key均滿足堆定義*//*調整R[low]的位置使之成為小根堆*/{R[0]=R[low];/*臨時保存調整點R[low]*/for(k=2*low;k<=high;k=k*2){if((k<high)&&(LT(R[k+1].key,R[k].key))k++;/*選擇左、右孩子中關鍵字的最小者*/if(LT(R[k].key,R[0].key)){R[j]=R[k];low=k;}elsebreak;}R[j]=R[0];}2.堆的建立利用篩選算法，可以將任意無序的記錄序列建成一個堆，設R[1],R[2],…,R[n]是待排序的記錄序列。將二叉樹的每棵子樹都篩選成為堆。只有根結點的樹是堆。第?n/2?個結點之后的所有結點都沒有子樹，即以第n/2個結點之后的結點為根的子樹都是堆。因此，以這些結點為左、右孩子的結點，其左、右子樹都是堆，則進行一次篩選就可以成為堆。同理，只要將這些結點的直接父結點進行一次篩選就可以成為堆…。只需從第n/2個記錄到第1個記錄依次進行篩選就可以建立堆。3.堆排序算法實現(xiàn)堆的根結點是關鍵字最小的記錄，輸出根結點后，是以序列的最后一個記錄作為根結點，而原來堆的左、右子樹都是堆，則進行一次篩選就可以成為堆。voidHeap_Sort(SqlistR){inti;for(i=n/2;i>0;ij--)Heap_adjust(R,i,n);/*初始建堆*/for(i=n;i>=1;i--){R[0]=R[1];R[1]=R[i];R[i]=R[0];/*堆頂與最后一個交換*/Heap_adjust(R,1,i-1);}}（五）快速排序1.排序思想通過一趟排序，將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，再分別對這兩部分記錄進行下一趟排序，以達到整個序列有序。2.排序過程設待排序的記錄序列是R[s…t]，在記錄序列中任取一個記錄(一般取R[s])作為參照(又稱為基準或樞軸)，以R[s].key為基準重新排列其余的所有記錄，方法是：◆所有關鍵字比基準小的放R[s]之前；◆所有關鍵字比基準大的放R[s]之后。以R[s].key最后所在位置i作為分界，將序列R[s…t]分割成兩個子序列，稱為一趟快速排序。3.一趟快速排序方法從序列的兩端交替掃描各個記錄，將關鍵字小于基準關鍵字的記錄依次放置到序列的前邊；而將關鍵字大于基準關鍵字的記錄從序列的最后端起，依次放置到序列的后邊，直到掃描完所有的記錄。設置指針low，high，初值為第1個和最后一個記錄的位置。設兩個變量i，j，初始時令i=low，j=high，以R[low].key作為基準(將R[low]保存在R[0]中)。①從j所指位置向前搜索：將R[0].key與R[j].key進行比較：◆若R[0].key≤R[j].key：令j=j-1，然后繼續(xù)進行比較，直到i=j或R[0].key>R[j].key為止；◆若R[0].key>R[j].key：R[j]R[i]，騰空R[j]的位置，且令i=i+1；②從i所指位置起向后搜索：將R[0].key與R[i].key進行比較：◆若R[0].key≥R[i].key：令i=i+1，然后繼續(xù)進行比較，直到i=j或R[0].key<R[i].key為止；◆若R[0].key<R[i].key：R[i]R[j]，騰空R[i]的位置，且令j=j-1；重復①、②，直至i=j為止，i就是R[0](基準)所應放置的位置。4.算法實現(xiàn)⑴一趟快速排序算法的實現(xiàn)intquick_one_pass(SqlistR,intlow,inthigh){inti=low,j=high;R[0]=R[i];/*R[0]作為臨時單元和哨兵*/do{while(LQ(R[0].key,R[j].key)&&(j>i))j--;if(j>i){R[i]=R[j];i++;}while(LQ(R[i].key,R[0].key)&&(j>i))i++;if(j>i){R[j]=R[i];j--;}}while(i!=j);/*i=j時退出掃描*/R[i]=R[0];return(i);}⑵快速排序算法實現(xiàn)當進行一趟快速排序后，采用同樣方法分別對兩個子序列快速排序，直到子序列記錄個為1為止。①遞歸算法voidquick_Sort(SqlistR,intlow,inthigh){intk;if(low<high){k=quick_one_pass(R,low,high);quick_Sort(R,low,k-1);quick_Sort(R,k+1,high);}/*序列分為兩部分后分別對每個子序列排序*/}②非遞歸算法voidquick_Sort(SqlistR,intlow,inthigh){intk,stack[MAX_STACK],top=0;do{while(low<high){k=quick_one_pass(R,low,high);stack[++top]=high;stack[++top]=k+1;/*第二個子序列的上,下界分別入棧*/high=k-1;}if(top!=0){low=stack[top--];high=stack[top--];}}while(top!=0&&low<high);}源程序清單：#include<stdio.h>#include<stdlib.h>#defineMAX_SIZE100typedefstructRecType{ intkey;//關鍵字碼 charotherinfo;//其他域}RecType;typedefstruct{ RecTypeR[MAX_SIZE]; intn;}Sqlist;voidstraight_insert_sort(SqlistL,intn){//直接插入排序 inti,j; for(i=2;i<=n;i++){ L.R[0]=L.R[i];j=i-1; while(L.R[0].key<L.R[j].key){ L.R[j+1]=L.R[j]; j--; } L.R[j+1]=L.R[0]; } for(i=1;i<=n;i++) printf("%d%c\n",L.R[i].key,L.R[i].otherinfo);}voidshell_pass(Sqlist&L,intn,intd){//一趟希爾排序 intj,k; for(j=d+1;j<=n;j++){ L.R[0]=L.R[j]; k=j-d; while((k>0)&&(L.R[0].key<L.R[k].key)){ L.R[k+d]=L.R[k];k=k-d; } L.R[k+d]=L.R[0]; }}voidshell_sort(Sqlist&L,intn,intdk[],intt){//希爾排序 inti,j,m; for(m=0;m<t;m++){ shell_pass(L,n,dk[m]); for(j=1;j<=n;j++) printf("%3d",L.R[j].key); printf("\n"); } for(i=1;i<=n;i++) printf("%d%c\n",L.R[i].key,L.R[i].otherinfo);}voidsimple_selection_sort(SqlistL,intn){//直接選擇排序 inti,j,k; for(i=1;i<n;i++){ k=i; for(j=i+1;j<=n;j++) if(L.R[j].key<L.R[k].key)k=j; if(k!=i){ L.R[0]=L.R[k];L.R[k]=L.R[i]; L.R[i]=L.R[0]; } } for(i=1;i<=n;i++) printf("%d%c\n",L.R[i].key,L.R[i].otherinfo);}voidHeap_adjust(Sqlist&L,intlow,inthigh){//堆調整 intk; L.R[0]=L.R[low]; for(k=2*low;k<=high;k=k*2){ if((k<high)&&(L.R[k+1].key<L.R[k].key)) k++; if(L.R[k].key<L.R[0].key){ L.R[low]=L.R[k];low=k;} elsebreak; } L.R[low]=L.R[0];}voidHeap_Sort(Sqlist&L,intn){//堆排序 inti,j; for(i=n/2;i>0;i--) Heap_adjust(L,i,n);for(i=n;i>=1;i--){ L.R[0]=L.R[1];L.R[1]=L.R[i]; L.R[i]=L.R[0]; Heap_adjust(L,1,i-1); for(j=n;j>=1;j--) printf("%3d",L.R[j].key); printf("\n");} for(i=n;i>=1;i--) printf("%d%c\n",L.R[i].key,L.R[i].otherinfo);}intquick_one_pass(Sqlist&L,intlow,inthigh){//一趟快速排序 inti=low,j=high; L.R[0]=L.R[i]; do{ while((L.R[0].key<=L.R[j].key)&&(j>i)) j--; if(j>i){L.R[i]=L.R[j];i++;} while((L.R[i].key<=L.R[0].key)&&(j>i)) i++; if(j>i){L.R[j]=L.R[i];j--;} }while(i!=j); L.R[i]=L.R[0];return(i);}voidquick_Sort(Sqlist&L,intn,intlow,inthigh){//快速排序 inti,k; if(low<high){ k=quick_one_pass(L,low,high); quick_Sort(L,n,low,k-1); quick_Sort