《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告——排序(共11頁(yè)).docx》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告——排序(共11頁(yè)).docx（11頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1實(shí)驗(yàn)要求【實(shí)驗(yàn)?zāi)康摹?學(xué)習(xí)、實(shí)現(xiàn)、對(duì)比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。【實(shí)驗(yàn)內(nèi)容】使用簡(jiǎn)單數(shù)組實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法： 1、插入排序 2、希爾排序3、冒泡排序4、快速排序5、簡(jiǎn)單選擇排序6、堆排序（選作）7、歸并排序（選作）8、基數(shù)排序（選作）9、其他要求： 1、測(cè)試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)2、對(duì)于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)（其中關(guān)鍵字交換計(jì)為3次移動(dòng)）。 3、對(duì)于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時(shí)間，精確到微秒（選作）4、對(duì)2和3的結(jié)果進(jìn)行分析，驗(yàn)證上述各種算法的

2、時(shí)間復(fù)雜度編寫測(cè)試main()函數(shù)測(cè)試線性表的正確性。2. 程序分析2.1 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)：數(shù)組r1r2 ri-1 ri ri+1 rn有序區(qū) 無(wú)序區(qū) 圖8-1 直接插入排序的基本思想圖解插入到合適位置2.2 關(guān)鍵算法分析/插入排序void InsertSort(int r, int n)int count1=0,count2=0;for (int i=2; i<n; i+) r0=ri; /設(shè)置哨兵for (int j=i-1; r0<rj; j-) /尋找插入位置rj+1=rj; /記錄后移rj+1=r0;count1+;count2+;for(int k=1;k<n

3、;k+)cout<<rk<<" "cout<<endl;cout<<"比較次數(shù)為 "<<count1<<" 移動(dòng)次數(shù)為 "<<count2<<endl;/希爾排序void ShellSort(int r, int n)int i;int d;int j;int count1=0,count2=0; for (d=n/2; d>=1; d=d/2) /以增量為d進(jìn)行直接插入排序for (i=d+1; i<n; i+) r0=ri;

4、 /暫存被插入記錄for (j=i-d; j>0 && r0<rj; j=j-d)rj+d=rj; /記錄后移d個(gè)位置rj+d=r0;count1+;count2=count2+d;count1+;for(i=1;i<n;i+)cout<<ri<<" "cout<<endl;cout<<"比較次數(shù)為 "<<count1<<" 移動(dòng)次數(shù)為 "<<count2<<endl;r1r2 ri-1 ri ri+1 r

5、n有序區(qū) 無(wú)序區(qū) 圖8-1 直接插入排序的基本思想圖解插入到合適位置/起泡排序void BubbleSort(int r, int n)int temp;int exchange;int bound;int count1=0,count2=0; exchange=n-1; /第一趟起泡排序的范圍是r1到rnwhile (exchange) /僅當(dāng)上一趟排序有記錄交換才進(jìn)行本趟排序bound=exchange; exchange=0; for(int j=0;j<bound;j+)/一趟起泡排序count1+;/接下來(lái)有一次比較if(rj>rj+1) temp=rj;/交換rj和rj

6、+1rj=rj+1;rj+1=temp;exchange=j;/記錄每一次發(fā)生記錄交換的位置count2=count2+3;/移動(dòng)了3次for(int i=1;i<n;i+)cout<<ri<<" "cout<<endl;cout<<"比較次數(shù)為 "<<count1<<" 移動(dòng)次數(shù)為 "<<count2<<endl;/快速排序一次劃分int Partition(int r, int first, int end,int &co

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

8、count1+;count1+;if (i<j)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 (first<end) /遞歸結(jié)束int pivot=Partition(r, first, end,count1,count2); /一次劃分QuickSort(r, first, pivot-1,count1,count

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

10、or(j=i+1;j<n;j+)/在無(wú)序區(qū)中選取最小記錄count1+;/比較次數(shù)加一 if(rj<rindex)/如果該元素比現(xiàn)在第i個(gè)位置的元素小index=j;count1+;/在判斷不滿足循環(huán)條件j<n時(shí)，比較了一次 if(index!=i) temp=ri;/將無(wú)序區(qū)的最小記錄與第i個(gè)位置上的記錄交換 ri=rindex; rindex=temp;count2=count2+3;/移動(dòng)次數(shù)加3 for(i=1;i<n;i+)cout<<ri<<" "cout<<endl; cout<<&quo

11、t;比較次數(shù)為 "<<count1<<" 移動(dòng)次數(shù)為 "<<count2<<endl;/篩選法調(diào)整堆void Sift(int r,int k,int m,int &count1,int &count2)/s，t分別為比較和移動(dòng)次數(shù)int i;int j;int temp;i=k; j=2*i+1; /置i為要篩的結(jié)點(diǎn)，j為i的左孩子while(j<=m)/篩選還沒有進(jìn)行到葉子if(j<m && rj<rj+1) j+;/比較i的左右孩子，j為較大者count1=count1+2;/該語(yǔ)句之前和之后分別有一次比較if(ri>rj)break;/根結(jié)點(diǎn)已經(jīng)大于左右孩子中的