數據結構實驗報告-排序

1、北京郵電大學電信工程學院第 頁第 頁2008級數據結構實驗報告實驗名稱：實驗四排序學生姓名：班級：班內序號：學號：日期：2009年12月6日1實驗要求實驗目的通過實現下述實驗內容，學習、實現、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。實驗內容使用簡單數組實現下面各種排序算法，并進行比較。排序算法：1、插入排序2、希爾排序3、冒泡排序4、快速排序5、簡單選擇排序6、堆排序（選作）7、歸并排序（選作）8、基數排序（選作）9、其他2.程序分析2.1存儲結構存儲結構：順序存儲結構示意圖如下：aOala2ai3a4a5a62.2關鍵算法分析順序數組存儲結構核心算法思想：利用教材講

2、述的基本算法思想，實現七種排序算法，統計其運行相關數據。將七種排序函數入口地址作為函數指針數組，實現快速調用和統計。使得程序代碼可讀性增、結構更加優(yōu)化。關鍵算法思想描述和實現：關鍵算法：實現七種算法的基本排序功能。1、插入排序：依次將待排序的序列中的每一個記錄插入到先前排序好的序列中，直到全部記錄排序完畢。2、希爾排序：先將整個序列分割成若干個子列，分別在各個子列中運用直接插入排序,待整個序列基本有序時，再對全體記錄進行一次直接插入排序。3、冒泡排序：兩兩比較相鄰記錄的關鍵碼，如果反序則交換，直到沒有反序記錄為止。4、快速排序：首先選擇一個基準，將記錄分割為兩部分，左支小于或等于基準，右支則大

3、于基準，然后對兩部分重復上述過程，直至整個序列排序完成。5、選擇排序：從待排序的記錄序列中選擇關鍵碼最?。ɑ蜃畲螅┑挠涗洸⑺c序列中的第一個記錄交換位置;然后從不包括第一個位置上的記錄序列中選擇關鍵碼最?。ɑ蜃畲螅┑挠涗洸⑺c序列中的第二個記錄交換位置;如此重復,直到序列中只剩下一個記錄為止。6、堆排序：通過建立大根堆或者小根堆，取出根節(jié)點，反復調整堆使之保持大根堆或者小根堆，直至最后序列有序。7、歸并排序：將若干個有序序列兩兩歸并，直至所有待排序的記錄都在一個有序序列為止。C+實現：關鍵算法2：獲取當前系統時間，精確到微秒，分別在代碼運行前后調用記錄前后時間，再相減即可得到代碼運行時間。

4、此處調用函數QueryPerformanceCounter（）用于得到高精度計時器的值。C+實現：關鍵算法3：試圖尋求最簡短的代碼以實現多達七種排序算法的簡單調用、亂序和順序以及逆序數據的分別排序和性能指標統計、算法時間的精確而簡易的統計、算法移動次數和比較次數的精確統計。如果設計不合理，將使得主調函數的調用代碼冗長，可讀性變差。采用以下三種方法實現：使用函數指針數組，分別指向各排序函數的入口地址，然后在Statistics。函數中加以調用，使得排序函數運行在統計時間函數之間，這樣使用一個for語句即可實現七種算法的一次性調用、時間統計、移動次數和比較次數統計。C+實現：voidStatist

5、ics(Sort&obj,inti,intj)obj.startTime=obj.GetNowTime();(obj.*pFunctioni)(obj.pRandoml);obj.endTime=obj.GetNowTime();obj.runtimeij=obj.endTime-obj.startTime;使用兩個數組實現亂序、順序以及逆序數據的排序，大大節(jié)省了空間的消耗?；舅枷霝椋弘S機序列產生一個指定長度的亂序序列，然后通過memcpy()函數拷貝到第二個數組里，第二個數組作為亂序序列的保存數組，每次對第一個數組進行排序，之后拷貝第二個數組中的亂序序列到第一個數組，實現各次亂序排列。只要

6、算法正確(第一步可以檢驗)，之后順序排列只需反復對第一個數組進行操作即可，再后用第二個數組保存逆序數組，然后同樣在每次排序之后復制第二數組存儲的亂序序列到第一組，對第一組反復排序即可。C+實現：請參看源代碼。建立兩個數組分別統計運行次數，再統一使用一個數組記錄七種算法在三種不同數據情況下的移動次數和交換次數。在分別運行亂序、順序和逆序數組排序時取出前兩個數組的值寫入第三個數組，然后置零繼續(xù)統計。C+實現：請參看源代碼。時間復雜度與空間復雜度：理論分析可以得出各種排序算法的時間復雜度和空間復雜度，如下表所示:排序方法平均情況最好情況最壞情況輔助空間直接插入排序On2OnOn2O1希爾排序Onlo

7、ggnOn2Oni3On2O1起泡排序On2O(n)On2O1快速排序Onlog2nOnlog2nOn2Olog2nOn簡單選擇排序On2On2On2O1堆排序Onlog2nOnlog2nO(nlog2n)O1歸并排序Onlog2nOnlog2nOnlog2nOn3.程序運行框圖:北京郵電大學電信工程學院第 #頁第 頁實際測試和分析：實際運行結果如下：（其中隨機產生的數據量為1000）北京郵電大學電信工程學院第 #頁第 #頁SjjC:Windov*5s,stem32rmd.北京郵電大學電信工程學院第 #頁第 #頁北京郵電大學電信工程學院第 #頁第 #頁順將$時繼續(xù)日、;、訥3047424116

8、5344050705943732B17014596850355702515928277125125080554G531249北京郵電大學電信工程學院第 #頁第 #頁北京郵電大學電信工程學院第 頁第 #頁1、多次運行之后統計，從亂序的時間消耗來看，基本符合理論分析。參看圖一。2、由于加入了統計次數的代碼，勢必增加時間開銷，這樣統計出來的時間將有一定的誤差。假若比較次數和移動次數相差較多，則將產生較大的實驗誤差。故重新寫了代碼，沒有加入比較次數和移動次數的比較的代碼，運行結果如圖二所示，均采用隨機產生的1000個亂序數據進行排序?？梢钥闯鰰r間有所減少。因而圖二更加接近實際。3、本程序中的代碼有的采

9、用了遞歸的形式，如果考慮用棧來模擬的話，效率會有提升，所以運行時間還和代碼的實現有關，代碼本身只是描述了算法思想，并沒有再進行編寫方面的優(yōu)化，因而還不能完全反映出每個算法的根本性能。4.1、在初期構思代碼的時候，首先構造了各種算法的基本實現代碼，封裝成類，已經能夠實現七種排序的基本功能，并且測試無誤。后來考慮能否優(yōu)化本程序，首先考慮到測試算法的需求，需要大量隨機數，因為增添了隨機函數發(fā)生器，滿足各種測試條件的需求。之后考慮如何能簡化代碼以實現多達七種排序算法的簡單調用、亂序和順序以及逆序數據的分別排序和性能指標統計、算法時間的精確而簡易的統計、算法移動次數和比較次數的精確統計。如果設計不合理，

10、將使得主調函數的調用代碼冗長，可讀性變差。因而采用了函數指針數組和統一的接口函數，采用二維數組存儲移動次數和比較次數，調用精確的系統函數實現時間的統計。此外還添加了一些列優(yōu)化，特別是函數封裝的方法，使得程序的結構變得更加合理，版面風格也變得好看，可讀性增強。2、程序的優(yōu)化是一個艱辛的過程，如果只是實現一般的功能，將變得容易很多，當加上優(yōu)化，不論是效率還是結構優(yōu)化，都需要精心設計。這次做優(yōu)化的過程中，遇到不少阻力。由于優(yōu)化中用到很多類的封裝和訪問控制方面的知識，而這部分知識恰好是大一一年學習的薄弱點。因而以后要多花力氣學習C+編程語言，必須要加強這方面的訓練，這樣才能在將編程思想和數據結構轉換為

11、代碼的時候能得心應手。3、改進：本程序代碼設計時運用了遞歸的調用方式，效率還可以通過將其轉換為棧模擬的方式得以提高。在實現類的封裝的時候為了共享數據采用了友元函數的方式，考慮能否使用其他方式使得類的封裝更加完善。北京郵電大學電信工程學院第 頁第 頁附錄源碼：(包括三個cpp文件)/Main.cpp#includeviostreamusingnamespacestd;#includeSort.h#includevtime.h#includevstring.hstaticint(Sort:*pFunction7)(longint)=&Sort:InsertSort,&Sort:ShellSort,

12、&Sort:BubbleSort,&Sort:QuickSort,&Sort:SelectSort,&Sort:HeapSort，&Sort:MergeSort;char*funcName7=l、插入排序:,2、希爾排序:,3、冒泡排序:,4、快速排序:,5、選擇排序:,6、堆排序:,7、歸并排序:;/*統計時間函數*/voidStatistics(Sort&obj,inti,intj)obj.startTime=obj.GetNowTime();(obj.*pFunctioni)(obj.pRandom1);obj.endTime=obj.GetNowTime();obj.runtimeij

13、=obj.endTime-obj.startTime;intmain(void)coutvv程序說明：nl、默認產生10個隨機數，如需加大數據量，請修改常量Max;n2、默認打印排序的結果以顯示算法正確與否，如果想不打印，請注釋相關語句。nn;Sortobj;obj.CreateData();memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(longint);inti(0),j(0);/-11_,1_,Z-*11/平平平平平平平平平平平平平平平平平平平平平平平平平TjTi丫丫-A71|不不不不不不不不不不不不不不不不不不不不不不不不不不不不不不不不

14、不/obj.SetTimesZero();for(i=0;iv7;i+)Statistics(obj,i,0);coutvvfuncNameivvn;北京郵電大學電信工程學院第 #頁第 #頁北京郵電大學電信工程學院第 頁第 頁obj.PrintArray(obj.pRandom1);if(i!=6)memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(longint);obj.RecordTimes(O);obj.SetTimesZero();for(i=0;i#include#includevtime.h#include#include#includ

15、evwindows.h#include#includeviomanip北京郵電大學電信工程學院北京郵電大學電信工程學院第 #頁第 頁usingnamespacestd;/*構造函數/TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTx/Sort:Sort()memset(timestable,0,sizeof(int)*7*6);/*構造數組/TxTxTxTxTxTxT

16、xTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTx/voidSort:CreateData(void)pRandoml=newlongintMax+l;pRandom2=newlongintMax+1;srand(unsigned)time(NULL);for(inti=1;i=Max;i+)pRandom2i=rand();coutvv隨機亂序數組如下：n;如果不輸出原始數組，請注釋掉此兩行

17、PrintArray(pRandom2);/*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*，弋/、*、r/t!*T*XI*-1卜I*/*簡單插廿入排匚序/TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxT

18、x/intSort:InsertSort(longintparray)北京郵電大學電信工程學院北京郵電大學電信工程學院第 頁第 #頁intj=0;for(inti=2;i=1;d/=2)for(inti=d+1;i0&parray0parrayj+1)parray0=parrayj;parrayj=parrayj+1;parrayj+1=parray0;exchange=j;movetimes2+=3;return0;/jKItiI；I*-1r*_/TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxiI，J.

19、I-|III-*丫、*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*/TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTx/intSort

20、:QuickSort(longintparray)QuickSortRecursion(parray,1,Max);return0;intSort:QuickSortRecursion(longintparray,intfirst=l,intend=Max)if(firstvend)intpivot=QuickSortPatition(parray,first,end);QuickSortRecursion(parray,first,pivot-1);左側子序列排序QuickSortRecursion(parray,pivot+1,end);右側子序列排序return0;intSort:Qui

21、ckSortPatition(longintr,intfirst,intend)inti=first;intj=end;inttemp;while(ij)while(ij&ri=rj)j-;comparetimes3+;北京郵電大學電信工程學院北京郵電大學電信工程學院第 頁第 #頁北京郵電大學電信工程學院北京郵電大學電信工程學院第 #頁第 頁if(ij)temp=ri;ri=rj;rj=temp;i+；movetimes3+=3;while(ij&ri=rj)i+；comparetimes3+;if(ij)temp=rj;rj=ri;ri=temp;j-;movetimes3+=3;右側掃描將

22、較小記錄交換到前面左側掃描將較大記錄交換到后面北京郵電大學電信工程學院北京郵電大學電信工程學院movetimes4+=3;第 頁movetimes4+=3;第 #頁returni;i為軸值記錄的最終位置北京郵電大學電信工程學院北京郵電大學電信工程學院movetimes4+=3;第 #頁movetimes4+=3;第 #頁北京郵電大學電信工程學院北京郵電大學電信工程學院movetimes4+=3;第 #頁movetimes4+=3;第 #頁北京郵電大學電信工程學院北京郵電大學電信工程學院movetimes4+=3;第 #頁movetimes4+=3;第 #頁北京郵電大學電信工程學院北京郵電大學電

23、信工程學院movetimes4+=3;第 #頁movetimes4+=3;第 #頁intSort:SelectSort(longintparray)inti,j,index,temp;北京郵電大學電信工程學院北京郵電大學電信工程學院movetimes4+=3;第 #頁movetimes4+=3;第 #頁北京郵電大學電信工程學院北京郵電大學電信工程學院movetimes4+=3;第 #頁movetimes4+=3;第 #頁for(i=1;ivMax;i+)對n個記錄進行n-1趟簡單選擇排序北京郵電大學電信工程學院北京郵電大學電信工程學院movetimes4+=3;第 #頁movetimes4+=

24、3;第 #頁北京郵電大學電信工程學院北京郵電大學電信工程學院movetimes4+=3;第 #頁movetimes4+=3;第 頁index=i;for(j=i+1;j=Max;j+)comparetimes4+;在無序區(qū)中選取最小記錄if(parrayj=l;i-)HeapSortSift(parray,i,Max);for(i=1;iMax;i+)parray0=parrayMax-i+1;parrayMax-i+1=parray1;parray1=parray0;movetimes5+=3;HeapSortSift(parray,1,Max-i);return0;voidSort:Hea

25、pSortSift(longintparray,intk,intm)inti,j;i=k;j=2*i;置i為要篩的結點，j為i的左孩子while(j=m)篩選還沒有進行到葉子if(jm&parrayjparrayj)comparetimes5+;break;根結點已經大于左右孩子中的較大者elseparray0=parrayi;parrayi=parrayj;parrayj=parray0;i=j；被篩結點位于原來結點j的位置j=2*i;/777777777777777777777777fI1i4I*-1r*_,/TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTx

26、TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxII1|-II-丫、*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*/TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTx

27、TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTx/intSort:MergeSort(longintparray)longintrlMax+l;inth(1);while(hvMax)MergePass(parray,r1,h);歸并h=2*h;MergePass(r1,parray,h);h=2*h;return0;voidSort:Merge(longintparray,longintr1,ints,intm,intt)一次歸并北京郵電大學電信工程學院北京郵電大學電信工程學院第 頁第 頁北京郵電大學電信

28、工程學院movetimes6+;第 頁inti=s;intj=m+l;intk=s;while(iv=m&jv=t)comparetimes6+;movetimes6+;if(parrayi=parrayj)r1k+=parrayi+;elser1k+=parrayj+;if(i=m)while(i=m)r1k+=parrayi+;elsewhile(j=t)rlk+=parrayj+;movetimes6+;voidSort:MergePass(longintparray,longintr1,inth)一趟歸并inti(1),k;while(iv=Max-2*h+1)Merge(parray

29、,r1,i,i+h-1,i+2*h-1);i+=2*h;f(ivMax-h+1)Merge(parray,r1,i,i+h-1,Max);elsefor(k=i;kL彳rJjI/*打印數組/TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTx/voidSort:PrintArray(longint*pRandom)for(intj=l;jv=Max;j+)coutvvpRandomjvvt;coutvvendl;/TxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTxTx/voidSort:SetTimesZero()memset(comparetimes,0,sizeof(int)*7);memset(movetimes,