《數(shù)據(jù)結構實驗報告——排序.docx》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構實驗報告——排序.docx（11頁珍藏版）》請在匯文網(wǎng)上搜索。

1、1實驗要求【實驗目的】 學習、實現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。【實驗內容】使用簡單數(shù)組實現(xiàn)下面各種排序算法，并進行比較。排序算法： 1、插入排序 2、希爾排序3、冒泡排序4、快速排序5、簡單選擇排序6、堆排序（選作）7、歸并排序（選作）8、基數(shù)排序（選作）9、其他要求： 1、測試數(shù)據(jù)分成三類：正序、逆序、隨機數(shù)據(jù)2、對于這三類數(shù)據(jù)，比較上述排序算法中關鍵字的比較次數(shù)和移動次數(shù)（其中關鍵字交換計為3次移動）。 3、對于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時間，精確到微秒（選作）4、對2和3的結果進行分析，驗證上述各種算法的時間復雜度編寫測試main

2、()函數(shù)測試線性表的正確性。2. 程序分析2.1 存儲結構 存儲結構：數(shù)組r1r2 ri-1 ri ri+1 rn有序區(qū) 無序區(qū) 圖8-1 直接插入排序的基本思想圖解插入到合適位置2.2 關鍵算法分析/插入排序void InsertSort(int r, int n)int count1=0,count2=0;for (int i=2; in; i+) r0=ri; /設置哨兵for (int j=i-1; r0rj; j-) /尋找插入位置rj+1=rj; /記錄后移rj+1=r0;count1+;count2+;for(int k=1;kn;k+)coutrk ;coutendl;cout

3、比較次數(shù)為 count1 移動次數(shù)為 count2=1; d=d/2) /以增量為d進行直接插入排序for (i=d+1; i0 & r0rj; j=j-d)rj+d=rj; /記錄后移d個位置rj+d=r0;count1+;count2=count2+d;count1+;for(i=1;in;i+)coutri ;coutendl;cout比較次數(shù)為 count1 移動次數(shù)為 count2endl;r1r2 ri-1 ri ri+1 rn有序區(qū) 無序區(qū) 圖8-1 直接插入排序的基本思想圖解插入到合適位置/起泡排序void BubbleSort(int r, int n)int temp;in

4、t exchange;int bound;int count1=0,count2=0; exchange=n-1; /第一趟起泡排序的范圍是r1到rnwhile (exchange) /僅當上一趟排序有記錄交換才進行本趟排序bound=exchange; exchange=0; for(int j=0;jrj+1) temp=rj;/交換rj和rj+1rj=rj+1;rj+1=temp;exchange=j;/記錄每一次發(fā)生記錄交換的位置count2=count2+3;/移動了3次for(int i=1;in;i+)coutri ;coutendl;cout比較次數(shù)為 count1 移動次數(shù)為

5、 count2endl;/快速排序一次劃分int Partition(int r, int first, int end,int &count1,int &count2)int i=first; /初始化 r1 ri-1 ri ri+1 rn 均ri 軸值 均ri 位于最終位置 圖8-6 快速排序的基本思想圖解int j=end;int temp; while (ij) while (ij & ri= rj)j-; /右側掃描count1+;count1+;if (ij) temp=ri; /將較小記錄交換到前面ri=rj;rj=temp;i+; count2=count2+3;while (

6、ij & ri= rj) i+; /左側掃描count1+;count1+;if (ij)temp=rj;rj=ri;ri=temp; /將較大記錄交換到后面j-; count2=count2+3; return i; /i為軸值記錄的最終位置/快速排序void QuickSort(int r, int first, int end,int &count1,int &count2)if (firstend) /遞歸結束int pivot=Partition(r, first, end,count1,count2); /一次劃分QuickSort(r, first, pivot-1,count1

7、,count2);/遞歸地對左側子序列進行快速排序QuickSort(r, pivot+1, end,count1,count2); /遞歸地對右側子序列進行快速排序r1 r2 ri-1 ri ri+1 rmin rn 有序區(qū) 無序區(qū) 已經(jīng)位于最終位置 rmin為無序區(qū)的最小記錄 圖8-9 簡單選擇排序的基本思想圖解交換/簡單選擇排序void SelectSort(int r , int n) int i;int j;int index;int temp;int count1=0,count2=0; for (i=0; in-1; i+) /對n個記錄進行n-1趟簡單選擇排序 index=i;

8、 for(j=i+1;jn;j+)/在無序區(qū)中選取最小記錄count1+;/比較次數(shù)加一 if(rjrindex)/如果該元素比現(xiàn)在第i個位置的元素小index=j;count1+;/在判斷不滿足循環(huán)條件jn時，比較了一次 if(index!=i) temp=ri;/將無序區(qū)的最小記錄與第i個位置上的記錄交換 ri=rindex; rindex=temp;count2=count2+3;/移動次數(shù)加3 for(i=1;in;i+)coutri ;coutendl; cout比較次數(shù)為 count1 移動次數(shù)為 count2endl;/篩選法調整堆void Sift(int r,int k,in

9、t m,int &count1,int &count2)/s，t分別為比較和移動次數(shù)int i;int j;int temp;i=k; j=2*i+1; /置i為要篩的結點，j為i的左孩子while(j=m)/篩選還沒有進行到葉子if(jm & rjrj)break;/根結點已經(jīng)大于左右孩子中的較大者else temp=ri; ri=rj; rj=temp;/將根結點與結點j交換 i=j; j=2*i+1;/下一個被篩結點位于原來結點j的位置count2=count2+3;/移動次數(shù)加3/堆排序void HeapSort(int r,int n) int count1=0,count2=0;/計數(shù)器，計比較和移動次數(shù)int i;int temp;for(i=n/2;i=0;i-)/初始建堆，從最后一個非終端結點至根結點Sift(r,i,n,count1,count2) ; for(i=n-1; i0; i-)/重復執(zhí)行移走堆頂及重建堆的操作temp=ri;