1、數據結構課程設計實驗報告題目：排序（必做題）姓名： 學號：指導老師： 時間：2015.09.03目錄一、設計內容和要求3二、算法思想描述31.希爾排序32.快速排序33.堆排序44.歸并排序75.性能分析8三、程序結構10四、結果與分析10五、收獲與體會12一、 設計內容和要求設計內容：排序算法的實現與比較要求：編程希望實現希爾、快速、堆排序、歸并排序算法。要求隨機產生10000個數據存入數據文件，然后讀數據文件，分別采用不同的排序方法進行排序，將結果存入文件中。二、 算法思想描述1. 希爾排序先將整個待排序記錄序列分割成若干個子序列，在在序列內分別進行直接插入排序，待整個序列基本有序時，再對

2、全體記錄進行一次直接插入排序。圖解：2. 快速排序首先選一個樞軸k（即比較的基準），通過一趟排序將待排序記錄分割成獨立的兩部分，前一部分記錄的關鍵碼均小于或等于樞軸k，后一部分記錄的關鍵碼均大于或等于樞軸k，然后分別對這兩部分重復上述方法，直到整個序列有序。經過一次劃分后2區1區樞軸k再對1、2區分別再進行快速排序3. 堆排序篩選：假設當前要篩選結點的編號為k，堆中最后一個結點的編號為m，并且結點k的左右子樹均是堆（即rk+1 rm滿足堆的條件），則篩選算法用偽代碼可描述為：圖解：堆排序：堆排序的基本思想是：首先將待排序的記錄序列構造成一個堆，此時，選出了堆中所有記錄的最大者即堆頂記錄，然后將

3、它從堆中移走（通常將堆頂記錄和堆中最后一個記錄交換），并將剩余的記錄再調整成堆，這樣又找出了次大的記錄，以此類推，直到堆中只有一個記錄為止。（1） 用大根堆排序的基本思想 先將初始文件R1.n建成一個大根堆，此堆為初始的無序區 再將關鍵字最大的記錄R1（即堆頂）和無序區的最后一個記錄Rn交換，由此得到新的無序區R1.n-1和有序區Rn，且滿足R1.n-1.keysRn.key由于交換后新的根R1可能違反堆性質，故應將當前無序區R1.n-1調整為堆。然后再次將R1.n-1中關鍵字最大的記錄R1和該區間的最后一個記錄Rn-1交換，由此得到新的無序區R1.n-2和有序區Rn-1.n，且仍滿足關系R1

4、.n-2.keysRn-1.n.keys，同樣要將R1.n-2調整為堆。直到無序區只有一個元素為止。（2） 大根堆排序算法的基本操作： 初始化操作：將R1.n構造為初始堆； 每一趟排序的基本操作：將當前無序區的堆頂記錄R1和該區間的最后一個記錄交換，然后將新的無序區調整為堆（亦稱重建堆）。注意： 只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由后往前逐步擴大至整個向量為止圖解：4. 歸并排序歸并排序是一種借助“歸并”進行排

5、序的方法，其主要思想是：將若干有序序列逐步歸并，最終歸并為一個有序序列。歸并是將兩個或兩個以上的有序序列合并成一個有序序列的過程。基本思想：將一個具有n個待排序記錄的序列看成是n個長度為1的有序序列，然后進行兩兩歸并，得到n/2個長度為2的有序序列，再進行兩兩歸并，得到n/4個長度為4的有序序列，直至得到一個長度為n的有序序列為止。5. 性能分析n 由于計算機實現的排序算法，沒有標準的數據交換操作，因此用交換次數作為衡量性能的標準很不準確，這里計算移動次數，即內存發生賦值操作則計數一次。n 即使計算了內存的拷貝操作，實際的性能仍與很多因素關聯，因此，程序作了耗時測試，研究在排序表數據結構發生變

6、化時，算法消耗的時間隨之變化的規律。n 數據量對性能的影響：u 為降低其他因素的影響，每組數據均按比例平均分布。u 如：100個數據則分布在0，100，500個數據則分布在0，500。運行結果：希爾快速堆歸并比較次數103037502150324262508220100764703124853950063865078846438481000149161111918850872350001111947461011772255235100002609881629682555521204241500040672325177740050618934320000606881347716550780260

7、82925000809050474661705064334093移動次數102419733450233138531286100500303118367250048042109707344881000112924688150769976500084389285718707861808100002031866186118422513361615000325076974592849832086162000048234213401238842928723225000659156169596493845367232圖表表示：n 直觀分析：兩張折線圖可以看出，數據量在1000以內，各排序算法各方面性能都幾

8、乎一致。數據增多至一定值時，各算法開始各自的穩定增長，但相互之間有明顯差別。100015000時，希爾和堆排序仍有重疊跡象，15000后，按照希爾、堆、快速、歸并的順序，可近似認為前者斜率分別是后者的2倍。n 理論性能：移動操作時間、空間復雜度均遠超過比較操作，因此，以移動次數衡量，快速排序性能最好。綜合比較、移動次數來看，仍然是快速排序性能最好，歸并次之，但這僅是理論分析，實際運行時，還要考慮諸多因素，如歸并排序大量的遞歸函數調用及數據移動操作，會占用過多的CPU及時間，極大的影響性能。三、 程序結構四、 結果與分析當測試10000個數據時2次測試結果如下：當測試100000個數據時5次測試結果如下，可看出快速排序是4個中相對最快的排序方法：五、 收獲與體會1. 通過產生隨機數文件，我