數(shù)據(jù)結(jié)構(gòu)實驗報告用簡單數(shù)組實現(xiàn)下面各種排序算法

1、第第 頁coutvv關(guān)鍵字移動次數(shù)：vv3*cyvvendl;coutvv關(guān)鍵字比較次數(shù)：vv(2*n-1-cb)*cb/2vvendl;快速排序一次劃分intPartition(intr,intfirst,intend)inti=first;/初始化intj=end;inttemp;while(ij)while(ij&ri=rj)j-;db+;if(ij)temp=ri;ri=rj;rj=temp;i+;dy+;while(ij&ri=rj)i+;db+;if(ij)temp=rj;rj=ri;ri=temp;j-;dy+;/右側(cè)掃描/右側(cè)掃描/將較小記錄交換到前面/左側(cè)掃描/將較大記錄交換

2、到后面/快速排序voidQuickSort(intr,intfirst,intend)if(firstend)/遞歸結(jié)束intpivot=Partition(r,first,end);/一次劃分QuickSort(r,first,pivot-l);遞歸地對左側(cè)子序列進行快速排序QuickSort(r,pivot+1,end);/遞歸地對右側(cè)子序列進行快速排序簡單選擇排序voidSelectSort(intr,intn)intey=0,eb=0;inti;intj;intindex;inttemp;for(i=0;in-1;i+)/對n個記錄進行n-1趟簡單選擇排序eb+;index=i;for

3、(j=i+1;jn;j+)/在無序區(qū)中選取最小記錄if(rjrindex)index=j;if(index!=i)temp=ri;ri=rindex;rindex=temp;ey+;for(i=0;in;i+)coutri;coutn;coutvv關(guān)鍵字移動次數(shù)：vv3*eyvvendl;coutvv關(guān)鍵字比較次數(shù)：vveb*(eb+l)/2vvendl;排序方法平均情況最好情況最壞情況輔助空間直接插入排序O(n2)O(n)O(n2)O(1)希爾排序O(nlog2n)O(n2)O(ni.3)O(n2)O(1)起泡排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n

4、)O(n2)O(log2n)O(n)簡單選擇排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)排序方法最好情況最壞情況平均情況直接插入排序O(n)O(n2)O(n2)起泡排序0O(n2)O(n2)簡單選擇排序0O(n)O(n)3.程序運行結(jié)果排序數(shù)據(jù)直接排序希爾排序起泡排序快速排序簡單選擇排序程序結(jié)束平均情況下快速排序為最優(yōu)排序4總結(jié)排序過程通常要進行下列兩種基本操作1.關(guān)鍵碼之間的比較2.移動;記錄從一個位置移動到另一個位置。所以在待排序的個數(shù)一定的情況下，算法的執(zhí)行時間主要消耗在關(guān)鍵碼之間的比較和記錄的