1、畢業論文 各種排序算法性能比較 系 專業 姓名 班級 學號 指導教師 職稱 設計時間 目錄摘要2第一章 緒論31.1 研究的背景及意義31.2 研究現狀31.3 本文主要內容4第二章 排序基本算法52.1 直接插入排序52.1.1基本原理52.1.2排序過程52.1.3時間復雜度分析52.2 直接選擇排序62.2.1基本原理62.2.2 排序過程62.2.3 時間復雜度分析62.3冒泡排序72.3.1基本原理72.3.2排序過程72.3.3 時間復雜度分析82.4 shell排序82.4.1基本原理82.4.2排序過程92.4.3時間復雜度分析92.5堆排序92.5.1基本原理92.5.2排序

2、過程102.5.3時間復雜度分析132.6快速排序132.6.1基本原理132.6.2排序過程142.6.3時間復雜度分析15第三章 系統設計163.1數據定義163.2 程序流程圖163.3 數據結構設計173.4 系統的模塊劃分及模塊功能實現173.4.1系統模塊劃分173.4.2各排序模塊功能實現18第四章 運行與測試29第五章 總結31致謝32參考文獻33 摘要排序算法是數據結構這門課程核心內容之一。它是計算機程序設計、數據庫、操作系統、編譯原理及人工智能等的重要基礎，廣泛應用于信息學、系統工程等各種領域。學習排序算法是為了將實際問題中涉及的對象在計算機中進行處理。本畢業論文對直接插入

3、排序、直接選擇排序、起泡排序、shell排序、快速排序以及堆排序算法進行比較。我們設置待排序表的元素為整數，用不同的測試數據做測試比較，長度取固定的三種，對象由隨機數生成，無需人工干預來選擇或者輸入數據。比較的指標為關鍵字的比較次數和關鍵字的移動次數。經過比較可以看到，當規模不斷增加時，各種算法之間的差別是很大的。這六種算法中，快速排序比較和移動的次數是最少的。也是最快的一種排序方法。堆排序和快速排序差不多，屬于同一個數量級。直接選擇排序雖然交換次數很少，但比較次數較多。關鍵字：直接插入排序；直接選擇排序；起泡排序；shell排序；快速排序；堆排序；第一章 緒論1.1 研究的背景及意義排序是計

4、算機程序設計中的一種重要操作。它的功能是將一個數據元素的任意序列，重新排列成一個按關鍵字有序的序列。排序算法是在整個計算機科學與技術領域上廣泛被使用的術語。排序算法是計算機程序設計、數據庫、操作系統、編譯原理及人工智能等的重要基礎，廣泛的應用于信息學、系統工程等各種領域。本人在研究各種算法的過程中，對其特點、效率、適用性等在不同的數據集上做全面的分析和比較，并以動態演示的方式展示一些經典排序算法運行過程，目的有以下五個方面：做算法的對比研究，培養研究能力；開發一個獨立的軟件，培養程序設計和軟件開發能力；初步掌握軟件開發過程的問題分析、系統設計、程序編碼、測試等基本方法和技能；提高綜合運用所學的

5、理論知識和方法獨立分析和解決問題的能力；為教學服務，研究結果對抽象的 算法與數據結構 的教學有一定的輔助作用。排序是計算機科學中最重要的研究問題之一, 它在計算機圖形、計算機輔助設計、機器人、模式識別及統計學等領域具有廣泛的應用。由于它固有的理論上的重要性,2000年它被列為對科學和工程計算的研究與實踐影響最大的10大問題之一。其功能是將一個數據元素的任意序列重新排列成一個按關鍵字有序的序列。1.2 研究現狀隨著計算機技術的日益發展，其應用早已不局限于簡單的數值運算。而涉及到問題的分析、數據結構框架的設計以及插入、刪除、排序、查找等復雜的非數值處理和操作。排序算法的學習就是為以后利用計算機資源

6、高效地開發非數值處理的計算機程序打下堅實的理論、方法和技術基礎。近來國內外專家學者們對排序算法又有了新的研究和發現。例如：我國山東大學的張峰和張金屯兩位教授共同研究了 我國植被數量分類和排序研究進展 這課題。很值得有關部門去學習和研究。1.3 本文主要內容排序的方法很多，但是就其全面性能而言，很難提出一種被認為是最好的方法，每一種方法都有各自的優缺點，適合在不同的環境下使用。如果排序中依據的不同原則對內部排序方法進行分類，則大致可分為直接插入排序、直接選擇排序、起泡排序、shell排序、快速排序、堆排序六類。本文編寫一個程序對直接插入排序、直接選擇排序、起泡排序、shell排序、快速排序及堆排

7、序這幾種內部排序算法進行比較，用不同的測試數據做測試比較。比較的指標為關鍵字的比較次數和關鍵字的移動次數。最后用圖表數據匯總，以便對這些內部排序算法進行性能分析。第二章 排序基本算法2.1 直接插入排序2.1.1基本原理假設待排序的n個記錄r0，r1，rn順序存放在數組中，直接插入法在插入記錄ri(i=1，2，n-1)時，記錄被劃分為兩個區間r0,ri-1和ri+1,rn-1,其中，前一個子區間已經排好序，后一個子區間是當前未排序的部分，將關鍵碼ki與ki-1ki-2，k0依次比較，找出應該插入的位置，將記錄ri插，然后將剩下的i-1個元素按關鍵詞大小依次插入該有序序列，沒插入一個元素后依然保

8、持該序列有序，經過i-1趟排序后即成為有序序列。每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子文件中的適當位置，直到全部記錄插入完成為止。2.1.2排序過程初始數據： 10 3 25 20 8 第一趟： 3 10 25 20 8 （將前兩個數據排序）第二趟： 3 10 25 20 8 （將 25 放入前面數據中的適當位置）第三趟： 3 10 20 25 8 （將 20 放入適當的位置）第四趟： 3 8 10 20 25 （將 8 放入適當的位置）2.1.3時間復雜度分析直接插入排序算法必須進行n-1趟。最好情況下，即初始序列有序，執行n-1趟，但每一趟只比較一次，移動元素兩次，

9、總的比較次數是(n-1)，移動元素次數是2(n-1)。因此最好情況下的時間復雜度就是o(n)。最壞情況(非遞增)下，最多比較i次，因此需要的比較次數是：所以，時間復雜度為o(n2)。 2.2 直接選擇排序2.2.1基本原理待排序的一組數據元素中，選出最小的一個數據元素與第一個位置的數據元素交換；然后在剩下的數據元素當中再找最小的與第二個位置的數據元素交換，循環到只剩下最后一個數據元素為止，依次類推直到所有記錄。第一趟第n個記錄中找出關鍵碼最小的記錄與第n個記錄交換；第二趟，從第二個記錄開始的，2 -1個記錄中再選出關鍵碼最小的記錄與第二個記錄交換；如此，第 i 趟，則從第i個記錄開始的 n -

10、 i + l個記錄中選出關鍵碼最小的記錄與第 i 個記錄交換，直到所有記錄排好序。2.2.2 排序過程初始數據 49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65 49第四趟排序后 13 27 38 49 49 97 65 76第五趟排序后 13 27 38 49 49 97 97 76第六趟排序后 13 27 38 49 49 76 76 97第七趟排序后 13 27 38 49 49 76 76 97最后排序結果 13 2

11、7 38 49 49 76 76 972.2.3 時間復雜度分析該算法運行時間與元素的初始排列無關。不論初始排列如何，該算法都必須執行n-1趟，每趟執行n-i-1次關鍵字的比較，這樣總的比較次數為：所以，簡單選擇排序的最好、最壞和平均情況的時間復雜度都為o(n2)。2.3冒泡排序2.3.1基本原理在每一趟冒泡排序中，依次比較相鄰的兩個關鍵字大小，若為反序咋交換。經過一趟起泡后，關鍵詞大的必須移到最后。按照這種方式進行第一趟在序列（i0in-1）中從前往后進行兩個相鄰元素的比較，若后者小，則交換，比較n-1次；第一趟排序結束，最大元素被交換到in-1中，下一趟只需在子序列（i0in-2）中進行；

12、如果在某一趟排序中未交換元素，則不再進行下一趟排序。將被排序的記錄數組j1 n垂直排列，每個記錄ji看作是重量為ji.key的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組r：凡掃描到違反本原則的輕氣泡，就使其向上飄浮。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止，最后可完成。2.3.2排序過程將被排序的記錄數組r1 n垂直排列，每個記錄ri看作是重量為ri.key的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組r：凡掃描到違反本原則的輕氣泡，就使其向上飄浮。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。（1）初始 r1.n為無序區。（2）第

13、一趟掃描 從無序區底部向上依次比較相鄰的兩個氣泡的重量，若發現輕者在下、重者在上，則交換二者的位置。即依次比較(rn，rn-1)，(rn-1，rn-2)，(r2，r1)；對于每對氣泡(rj+1，rj)，若rj+1.keyrj.key，則交換rj+1和rj的內容。 第一趟掃描完畢時，最輕的氣泡就飄浮到該區間的頂部，即關鍵字最小的記錄被放在最高位置r1上。（3）第二趟掃描 掃描r2,n。掃描完畢時，次輕的氣泡飄浮到r2的位置上,最后，經過n-1趟掃描可得到有序區r1n。 第i趟掃描時,r1i-1和rin分別為當前的有序區和無序區。掃描仍是從底部向上直至該區頂部。掃描完畢時，該區中最輕氣泡飄浮到頂部

14、位置ri上，結果是r1i變為新的有序區。初始數據 76 32 46 80 55 46* 第一輪：第一趟排序后 32 76 46 80 55 46* 第二趟排序后 32 46 76 80 55 46*第三趟排序后 32 46 76 80 55 46*第四趟排序后 32 46 76 55 80 46*第五趟排序后 32 46 76 55 46* 80第二輪排序結果 32 46 55 46* 76 80 第三輪排序結果 32 46 46 55 76 80 第四輪排序結果 32 46 46* 55 76 80 第五輪排序結果 32 46 46* 55 76 80 2.3.3 時間復雜度分析當原始數據正

15、向有序時，冒泡排序出現最好情況。此時，只需進行一趟排序，作n-1次關鍵字比較，因此最好情況下的時間復雜度是o(n)。當原始數據反向有序時，冒泡排序出現最壞情況。此時，需進行n-1趟排序，第i趟作(n-i)次關鍵字間的比較，并且需執行(n-i)次元素交換，所以，比較次數為：因此,最壞情況下的時間復雜度為o(n2)。2.4 shell排序2.4.1基本原理shell排序又稱縮小增量排序,shell排序法是以創建者donald shell的名字命名的.shell排序法是對相鄰指定距離(稱為間隔)的元素進行比較,已知到使用當前間隔進行比較的元素都按順序排序為止.shell把間隔縮小一半,然后繼續處理,

16、當間隔最終變為1,并且不再出現變化時,shell排序也就完成了其處理過程.先取一個整數d1n,把全部記錄分成d1個組，所有距離為d1倍數的記錄放在一組中，先在各組內排序；然后去d2d1重復上訴分組和排序工作；直至所取的增量dt=1(dtdt-ld2d1)，即所有記錄放在同一組中進行直接插入，直到dt=1，即所有記錄放在一組中為止。2.4.2排序過程先取一個正整數d1n，把所有序號相隔d1的數組元素放一組，組內進行直接插入排序；然后取d2d1，重復上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止。 初始數據：49 38 65 97 76 13 27 48 55 04 一趟結果(d

17、=5):13 27 48 55 04 49 38 65 97 76 二趟結果(d=3): 13 04 48 38 27 49 55 65 97 76 三趟結果(d=1): 04 13 27 38 48 49 55 65 76 972.4.3時間復雜度分析希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。所以，希爾排序的時間復雜度會比o(n2)好一些。由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自

18、的插入排序中移動，最后其穩定性就會被打亂，所以shell排序是不穩定的。所以希爾排序是不穩定的，其時間復雜度為o(n2)。2.5堆排序2.5.1基本原理堆排序思想很簡單，就是每次把關鍵詞調整為堆，取出堆頂元素與堆中最后一個元素交換，同時令堆得大小減一，把剩余的一些元素重新調整為堆，重復此過程，直到堆中只剩一個元素,n個關鍵字序列 kl , k2 ， ， kn稱為堆，當且僅當該序列滿足如下性質（簡稱為堆性質）: ( l) ki= k2i 且 ki= k2i 且 ki=k2i+1。若將此序列所存儲的向量 r 1n看作是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹:樹中非葉結點的關

19、鍵字均不大于（或不小于）其左右孩子（若存在）結點的關鍵字。根結點（亦稱為堆頂）的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。根結點（亦稱為堆頂）的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。注意： 堆中任一子樹亦是堆。 以上討論的堆實際上是二叉堆，類似地可定義 k 叉堆。2.5.2排序過程堆排序是一樹形選擇排序。堆排序的特點是：在排序過程中，將 r 1 n 看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之問的內在關系，在當前無序中選抒關鍵字最大（或最小）的記錄。下面將從實際數據中演示其排序中的各個操作。原始數組： 22 53 72 11 34 44 11 15

20、 28 3 10 65 第一步，從樹頂到樹葉把數填充進入，建立堆。紅色為下一次交換的兩個數（序列）。使記錄遞增有序，進一步排序。第一次交換：第二次交換：第三次交換：第四次交換：第五次交換：第六次交換：第七次交換：第八次交換：第九次交換：全程交換完成，得到最小值為 3 并且輸出它。從序列中刪除 3 ，重新建立堆。以次循環，直到全部輸出完成為止。2.5.3時間復雜度分析堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用heapify實現的。堆排序的最壞時間復雜度為o(nlogn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數較多，所以堆排序不適宜于記

21、錄數較少的文件。堆排序是不穩定的，算法時間復雜度o(nlogn)。2.6快速排序2.6.1基本原理首先我們選擇一個中間值 middle （程序中我們可使用數組中間值），把比中問值小的放在其左邊，比中問值大的放在其右邊。由于這個排序算法較復雜，我們先給出其進行一次排序的程序框架。在待排序的個記錄中任意取一個記錄（通常取第一個記錄）為區分標準，把所有小于該排序的記錄移到左邊，把所有大于該排序碼的記錄移到右邊，中級放所選記錄，為一趟快速排序。然后對前后兩個子序列分別重新上述過程，直到所有記錄都排好序。對任意給定的序列中某個元素，經過一趟排序后，將原序列分割成兩個子序列(rp(0),rp(1),rp(

22、s-1)和(rp(s+1),rp(s+2),rp(n-1)，其中前一個子序列中的所有元素的關鍵詞均小于或等于該元素的關鍵詞值kp(s)，后一個子序列中元素的關鍵詞均大于或等于kp(s)。稱該元素rp(s)為分割元素，子序列(rp(0),rp(1),rp(s-1)為其低端序列，(rp(0),rp(1),rp(s-1)為其高端序列。很明顯，以后只需對低端和高端序列分別進行快速排序，直到子序列為空或只有一個元素時結束，最后得到有序序列。總之，每趟使表的第一個元素放在適當位置，將表兩分，再對子表進行同樣的遞歸劃分，直至劃分的子表長度為1。2.6.2排序過程假設要排序的數組是a1an，首先任意選取一個數

23、據（通常選用第一個數據）作為關鍵數據，然后將所有比它小的數都放到它前面，所有比它大的數都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是： 1）設置兩個變量i、j，排序開始的時候i=1，j=n； 2）以第一個數組元素作為關鍵數據，賦值給x，即x=a1； 3）從j開始向前搜索，即由后開始向前搜索（j=j-1），找到第一個小于x的值，兩者交換； 4）從i開始向后搜索，即由前開始向后搜索（i=i+1），找到第一個大于x的值，兩者交換； 5）重復第3、4步，直到i=j； 例如：待排序的數組a的值分別是： a1 a2 a3 a4 a5 a6 a7： 49 38 65 97 76 13 27進行

24、第一次交換后：27 38 65 97 76 13 49 進行第二次交換后: 27 38 49 97 76 13 65進行第三次交換后：27 38 13 97 76 49 65進行第四次交換后：27 38 13 49 76 97 65此時再執行第三步的時候就發現i=j，從而結束一躺快速排序，那么經過一躺快速排序之后的結果是：27 38 13 49 76 97 65，即所以大于49的數全在49的后面，所以小于49的數全部在49的前面。快速排序就是遞歸調用此過程在以49為中點分割這個數據序列，分別對前面一部分和后面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最后把此數據序列變成一個有序

25、的序列，根據這種思想對于上述數組a的快速排序的全過程如下所示：初始狀態: 49 38 65 97 76 13 27 進行一次快速排序之后劃分為:27 38 13 49 76 97 65分別對前后兩部分進行快速排序: 13 27 38;97 76 652.6.3時間復雜度分析如果每一次分劃操作后，左、右兩個子序列的長度基本相等，則快速排序的效率最高，其最好情況時間復雜度為o(nlog2n)；反之，如果每次分劃操作所產生的兩個子序列，其中之一為空序列，此時，快速排序效率最低，其最壞情況時間復雜度為o(n2)。如果選擇左邊第一個元素為主元，則快速排序的最壞情況發生在原始序列正向有序或反向有序時。快速

26、排序的平均情況時間復雜度為o(nlog2n)。第三章 系統設計3.1數據定義輸入數據：由于大多數排序算法的時間開銷主要是關鍵字之間的比較和記錄的移動，算法的執行時間不僅依賴于問題的規模，還取決于輸入實例中數據的狀態。所以對于輸入數據，我們采用由用戶輸入記錄的個數（以關鍵字的數目分別為20，100，500為例），測試數據由隨機數產生器生成。輸出數據：產生的隨機數分別用直接插入排序；直接選擇排序；起泡排序；shell排序；快速排序；堆排序這些排序方法進行排序，輸出關鍵字的比較次數和移動次數。3.2 程序流程圖主程序產生1組隨機數起泡排序shell排序快速排序直接選擇排序堆排序記錄關鍵字的比較次數和

27、移動次數將隨機數保存在數組中循環20次輸出關鍵字的比較次數、移動次數的平均值直接插入排序 圖3.1 程序流程圖3.3 數據結構設計本程序中，考慮的內容就是待排序對象，排序的依據是關鍵字之間的大小比較，故在每個節點的類型定義中，至少得包含關鍵字key一項。不失一般性，這里就使用關鍵詞這一項，其他都省略，具體應用加上其他數據項即可。被排序對象是由一個個節點夠成，一個排序對象包含一系列指向一串節點的指針，排序對象的長度。本程序功能簡單。typedef structint key; /*關鍵字*/recordnode; /*排序節點的類型*/typedef structrecordnode *reco

28、rd;int n; /*排序對象的大小*/sortobject; /*排序節點的類型*/3.4 系統的模塊劃分及模塊功能實現3.4.1系統模塊劃分maininsertsortselectsortbubblesortsortmethodquicksortheapsortshellsortoutputquick圖3.2 系統模塊劃分圖3.4.2各排序模塊功能實現a直接插入排序void insertsort(sortobject *p,unsigned long *compare,unsigned long *exchange)int i,j;recordnode temp; sortobject

29、*pvector;if(pvector=(sortobject *)malloc(sizeof(sortobject)=null)printf(overfollow!);getchar();exit(1);for(i=0;in;i+)/* 復制數組*/pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;for(i=1;in;i+) temp=pvector-recordi; (*exchange)+; j=i-1; while(temp.keyrecordj.key)&(j=0) (*compare)+; (*excha

30、nge)+; pvector-recordj+1=pvector-recordj; j-; if(j!=(i-1) pvector-recordj+1=temp; (*exchange)+; free(pvector);當文件的初始狀態不同時，直接插入排序所耗費的時間是有很大差異的。最好情況是文件初態為正序，此時算法的時間復雜度為o(n)，最壞情況是文件初態為反序，相應的時間復雜度為o(n2)，算法的平均時間復雜度是o(n2)。算法的輔助空間復雜度是o(1)，是一個就地排序。b.直接選擇排序void selectsort(sortobject *p,unsigned long *compare

31、,unsigned long *exchange) int i,j,k; recordnode temp;sortobject *pvector;if(pvector=(sortobject *)malloc(sizeof(sortobject)=null) printf(overfollow!);getchar();exit(1); for(i=0;in;i+)/*復制數組*/ pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) (*comp

32、are)+; if(pvector-recordj.keyrecordk.key) k=j; if(k!=i) temp=pvector-recordi; pvector-recordi=pvector-recordk; pvector-recordk=temp; ( *exchange)+=3; free(pvector);選擇排序法的第一層循環從起始元素開始選到倒數第二個元素,主要是在每次進入的第二層循環之前,將外層循環的下標賦值給臨時變量,接下來的第二層循環中,如果發現有比這個最小位置處的元素更小的元素,則將那個更小的元素的下標賦給臨時變量,最后,在二層循環退出后,如果臨時變量改變,則說

33、明,有比當前外層循環位置更小的元素,需要將這兩個元素交換.c.冒泡排序void bubblesort(sortobject *p,unsigned long *compare,unsigned long *exchange) int i,j,noswap; recordnode temp; sortobject *pvector; if(pvector=(sortobject *)malloc(sizeof(sortobject)=null) printf(overfollow!); getchar(); exit(1); for(i=0;in;i+)/* 復制數組*/ pvector-rec

34、ordi=p-recordi; pvector-n=p-n; *compare=0; *exchange=0; for(i=0;in-1;i+) noswap=1; for(j=0;jn-i-1;j+) (*compare)+; if(pvector-recordj+1.keyrecordj.key) temp=pvector-recordj; pvector-recordj=pvector-recordj+1; pvector-recordj+1=temp; (*exchange)+=3; noswap=0; if(noswap) break; free(pvector);起泡排序的結束條件

35、為：最后一趟沒有進行“交換”。從起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經過一趟起泡，無序序列的長度只縮小1。 算法思想：將被排序的記錄數組r1.n垂直排列，每個記錄ji看作是重量為ji.key的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組j：凡掃描到違反本原則的輕氣泡，就使其向上飄浮。如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。dshell排序void shellsort(sortobject *p,int d,unsigned long *compare,unsigned long *exchange) in

36、t i,j,increment; recordnode temp; sortobject *pvector; if(pvector=(sortobject*)malloc(sizeof(sortobject)=null) printf(overfollow!); getchar(); exit(1); for(i=0;in;i+)/* 復制數組*/ pvector-recordi=p-recordi; pvector-n=p-n; *compare=0; *exchange=0; for(increment=d;increment0;increment/=2) for(i=increment;

37、in;i+) temp=pvector-recordi; (*exchange)+; j=i-increment; while(j=0&temp.keyrecordj.key) (*compare)+; pvector-recordj+increment=pvector-recordj; (*exchange)+;j-=increment; pvector-recordj+increment=temp; (*exchange)+; free(pvector);當增量d=1時，shellpass和insertsort基本一致，只是由于沒有哨兵而在內循環中增加了一個循環判定條件j0，以防下標越界。

38、e堆排序void heapsort(sortobject *p,unsigned long *compare,unsigned long *exchange)/*5.堆排序*/ int i,n; recordnode temp; sortobject *pvector; if(pvector=(sortobject *)malloc(sizeof(sortobject)=null) printf(overfollow!); getchar(); exit(1); for(i=0;in;i+)/* 復制數組*/ pvector-recordi=p-recordi;pvector-n=p-n;*c

39、ompare=0;*exchange=0;n=pvector-n;for(i=n/2-1;i=0;i-)siftheap(pvector,n,i,compare,exchange);/*首先構造第一個堆*/for(i=n-1;i0;i-) temp=pvector-record0; pvector-record0=pvector-recordi; pvector-recordi=temp; (*exchange)+=3; siftheap(pvector,i,0,compare,exchange);/*重建新堆*/free(pvector);當增量d=1時，shellpass和insertso

40、rt基本一致，只是由于沒有哨兵而在內循環中增加了一個循環判定條件j0，以防下標越界。f快速排序void quicksort(sortobject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)/*6.快速排序*/ int i,j; recordnode temp; if(left=right) return; i=left; j=right; temp=pvector-recordi; (*exchange)+; while(i!=j) while(pvector-recordj.key=t

41、emp.key)&(ji) (*compare)+; j-;if(irecordi+=pvector-recordj;(*exchange)+; while(pvector-recordi.keyi)(*compare)+;i+; if(irecordj-=pvector-recordi;.(*exchange)+; pvector-recordi=temp; (*exchange)+; quicksort(pvector,left,i-1,compare,exchange); quicksort(pvector,i+1,right,compare,exchange);對于n個成員，快速排序法

42、的比較次數大約為n*logn 次，交換次數大約為(n*logn)/6次。如果n為100，冒泡法需要進行4950 次比較，而快速排序法僅需要200 次，快速排序法的效率的確很高。快速排序法的性能與中間值的選定關系密切，如果每一次選擇的中間值都是最大值（或最小值），該算法的速度就會大大下降。快速排序算法最壞情況下的時間復雜度為o(n2)，而平均時間復雜度為o(n*logn)。g排序主調用函數上面說明各種排序函數都是在這里調用的。排序對象長度分別去20,100,500這三種，每種都有6中算法，每種算法都有兩個返還值：比較和移動次數，故這里定義了一個二維表number312，類型為unsigned l

43、ong型（因為比較次數和移動的次數最多可以超過百萬）。要產生一些不同的隨機數，必須開始調用函數randomize()初始隨機化種子，不然每次得到的隨機數都是一樣的。循環執行三次，每次都得到一種長度的比較移動次數。這里把快速排序放到最后調用，這樣，雖然調用此函數后排序對象是有序的，但不影響程序比較算法性能這一目的。最后，再用一個for循環把運行得到的比較結果輸出。用一個判斷語句，實現前面幾個在顯示后在出現的一個提示信息：“press any key to continue”，最后一個沒有提示，按任意鍵退出程序。void sortmethod(void) int i,j; unsigned lon

44、g num312=0; sortobject *pvector=(sortobject *)malloc(sizeof(sortobject); randomize(); for(j=0;j3;j+) for(i=0;irecordi.key=random(500); pvector-n=maxsortnumj; insertsort(pvector,&numj0,&numj1); selectsort(pvector,&numj2,&numj3); bubblesort(pvector,&numj4,&numj5); shellsort(pvector,4,&numj6,&numj7); h

45、eapsort(pvector,&numj8,&numj9); quicksort(pvector,0,maxsortnumj-1,&numj10,&numj11); printf(nsort method compare as follows:); for(j=0;j%-7ld exchanged-%-7ldn,numj0,numj1); printf(2.selectsort method: compared-%-7ld exchanged-%-7ldn,numj2,numj3); printf(3.bubblesort method: compared-%-7ld exchanged-%

46、-7ldn,numj4,numj5); printf(4.shellsort method: compared-%-7ld exchanged-%-7ldn,numj6,numj7); printf(5.heapsort method: compared-%-7ld exchanged-%-7ldn,numj8,numj9); printf(6.quicksort method: compared-%-7ld exchanged-%-7ldn,numj10,numj11); if(j!=2) printf(press any key to continue.n); getchar(); voi

47、d main() sortmethod(); 第四章 運行與測試此程序功能是比較各種排序算法的時間復雜度，長度取固定的三種，對象由隨機數生成，無需人工干預來選擇或者輸入數據。程序運行時出現如圖4.1所示界面。圖4.1 20個數據排序比較結果這是長度為20的6總排序算法的比較次數和移動次數統計，中間用逗號隔開。最下一行提示用戶還有待輸出數據“press any key to continue. ”，按任意鍵后繼續顯示。其中如若用冒泡排序，則要比較次數為175，交換次數為273次，這和冒泡排序比較次數3（n-i）=1/2（n*n-n）=190，交換次數為（n-i）=3/2（n*n-n）=270平均情形相近。而這種排序的改進方法快速排序的比較次數為31，交換次數51,顯然快速排序性能優于冒泡排序。類似分析長度可選為100和長度可選為500時各個算法的執行情況，分別作圖4.2和圖4.3所示圖4.2 100個數據排序比較結果圖4.3 500個數據排序比較結果可以看到，當規模不斷增加時，各種算法之間的差別是很大的。這六種算法中，快速排序比較和移動的次數是最少的。也是最快的一種排序方法。堆排序和快速排序差不多，屬于同一個數量級。直接選擇排序雖然交換次數很少，但比較次數較多。第五章 總結排序算法是是計算機程序設計、數據庫、操作系統、編譯原理及人工智能等的重要基礎，廣泛應用于信息學、系統工