程序設計排序算法分析

馮毅宏 楊英翔 劉冬莉 何彤

摘 要：排序算法是計算機程序設計的一個重要內容，對排序算法的分析與研究具有廣泛的應用價值。本文介紹了常見的排序算法，并通過對比分析，對各種排序算法從算法評價角度給出了綜合評價。

關鍵詞：排序算法；內部排序；對比分析；算法評價

排序是程序設計的常見問題，選擇合理高效的排序算法是數據處理的最重要的研究問題之一。排序算法的功能是將一個由一組數據元素或記錄組成的無序序列，重新排列成一個按關鍵字有序的序列[1]。有序序列可有效地提高記錄的查找效率。

1 排序算法分類

1.1 內部排序

內部排序是指待排序列完全存放在內存中所進行的排序過程，適合規模不太大的數據元素序列。內部排序可分為五類： 插入排序、交換排序、選擇排序、歸并排序和分配排序。

1.2 外部排序

外部排序是指待排序的序列無法一次裝入內存，需要在內存和外存之間進行多次數據交換，從而達到對序列中全部數據元素的排序。外部排序可將待排序序列分解成幾段能夠一次性裝人內存的待排序部分，然后對每一小段采用內部排序，再對已經排序的各子段進行歸并排序。即外部排序轉化為內部排序。因此需對內部排序進行更深入的研究分析。

2 常見的排序算法

2.1 插入排序

插入排序每次將一個待排序的數據元素，插入到前面已經排好序的序列中適當位置，使序列依然有序，直到待排序數據元素全部插入完為止。插入排序包括直接插入排序、折半插入排序和希爾排序。

（1）直接插入排序：將無序序列中的第一個數據元素依次插入到有序序列的合適位置，使有序序列仍然有序。

（2）折半插入排序：在有序序列中用折半法（二分法）查找待插入數據元素的位置。將處于有序序列中間位置數據元素的關鍵字和待排序數據元素的關鍵字比較，便把可插入的區間縮小一半，故稱為折半。折半插入排序僅減少了關鍵字間的比較次數，但數據元素的移動次數不變。

（3）希爾排序：先 取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1組。所有距離為d1的倍數的記錄放在同一組中。先在各組內進行直接插入排序，然后取第二個增量d2

2.2 交換排序

交換排序是指通過在數據元素之間互相交換逆序元素而進行的排序。交換排序包括冒泡排序和快速排序。

（1）冒泡排序：通過將相鄰的數據元素進行比較，若逆序則交換，逐步將無序序列處理成為有序序列。每一趟交換排序都會增加一個元素到有序區，整個冒泡排序過程最多需要進行n-1趟排序。

（2）快速排序：通過一趟排序將待排序的數據元素分割成獨立的兩部分，其中一部分數據元素的關鍵字均比另一部分數據元素的關鍵字小。則可分別對這兩部分元素繼續進行排序，以達到整個序列有序。

2.3 選擇排序

選擇排序是每一趟從待排序的數據元素中選出關鍵字最小（或最大）的一個元素，插入已排序序列的最后，直到n個數據元素全部插入已排序序列中。選擇排序包括簡單選擇排序、樹型選擇排序和堆排序。

（1）簡單選擇排序：從無序的序列中選取一個關鍵字最小的數據元素存放到有序序列中指定的位置。

（2）樹型選擇排序：又稱為錦標賽排序，是按錦標賽思想進行選擇排序的方法。先對n個數據元素的關鍵字進行兩兩比較，然后在其中的（n/2）個較小者間再進行兩兩比較，如此往復，直至選出最小關鍵字的數據元素為止。這個過程可用一棵n個結點的完全二叉樹來表示。

（3）堆排序：堆是滿足如下性質的完全二叉樹：樹中任一非葉子結點的關鍵字均大于等于其孩子結點的關鍵字。這種堆中根結點（稱為堆頂）的關鍵字最小，稱之為小根堆；反之，則稱之為大根堆。堆排序的算法是：將當前無序區調整為一個大根堆（或小根堆），選取關鍵字最大（或最小）的堆頂記錄，將它和無序區中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區是在原記錄區的尾部形成并逐步向前擴大到整個記錄區。

2.4 歸并排序

歸并排序是將兩個或兩個以上的有序序列合并成一個新的有序序列。歸并排序包括二路歸并排序和多路歸并排序。

（1）二路歸并排序：將兩個有序序列合并成一個新的有序序列。先從兩個有序序列中分別取第一個數據元素比較，關鍵字小（或大）的數據元素排入新的有序序列，同時在對應原序列中刪除該數據元素；然后再從兩個有序序列中分別取第一個數據元素比較，如此循環；當有一個序列為空時，則直接將另一個序列的數據元素依次取出即可。

（2）多路歸并排序：將多個有序序列合并成一個新的有序序列。通常用于外部排序。

2.5 分配排序

分配排序的排序過程無須比較關鍵字，而是通過分配和收集過程來實現排序。分配排序包括箱排序和基數排序。

（1）箱排序。

箱排序是設置若干個箱子，依次掃描待排序的數據元素R[0]，R[1]，…，R[n-1]，把關鍵字等于k的記錄全都裝入到第k個箱子里（分配），然后按序號依次將各非空的箱子首尾連接起來（收集）。

（2）基數排序

基數排序的算法是：一個邏輯關鍵字可以看成由若干個關鍵字復合而成的，可把每個排序關鍵字看成是一個d元組，即例如由關鍵字K由d個關鍵字（K0，K1，…，Kd-1）組成，排序時先按K0的值從小到大（或從大到小）將記錄分配到r個盒子中，然后依次收集這些記錄，再按K1的值分配到r個盒子中，如此反復，直到按Kd-1的值分配后收集起來的序列，便是完全排序的狀態，其中r稱為基數。基數的選擇和關鍵字的分解法因關鍵字的類型而異。基數排序分為最高位優先法和最低位優先法。

3 算法評價

3.1 穩定性

在待排序的序列中，若存在元素值相同的記錄，經過排序后，這些元素的相對次序不變，那么此算法為穩定的。冒泡排序、插入排序、歸并排序和基數排序是穩定的排序算法；選擇排序、快速排序、希爾排序、堆排序是不穩定的排序算法。

3.2 時間復雜度

時間復雜度是指執行算法所需要的計算工作量[3]。按平均情況下時間復雜度將排序分為四類：（1） 平方階（O（n2））排序：一般稱為簡單排序，如冒泡排序、簡單選擇排序和直接插入排序。（2） 線性對數階O（nlgn）排序：如快速排序、歸并排序和堆排序。（3） O（n1+￡）階排序：￡是介于0和1之間的常數，即0<￡<1，如希爾排序。（4）線性階（O（n））排序：如箱排序和基數排序。

3.3 空間復雜度

空間性能是排序所需輔助空間大小，所有簡單排序和堆排序都是O （1）；歸并排序和基數排序所需輔助空間最多，為O（n）。

4 結論

排序算法有很多，具體情況中使用哪一種算法很重要。為了選擇合適的算法，應順序考慮以下標準： 執行時間 ，存儲空間，編程工作量。數據量較小時，執行時間 和存儲空間差別不大，主要考慮編程工作量；當數據量大時， 執行時間為首要。相對來說，簡單排序中直接插入排序最好，快速排序最快，當序列為正序時，直接插入排序和冒泡排序都是較好選擇。

參考文獻

[1] 劉冬莉， 徐立輝. 大學計算機基礎教程[M]. 北京：清華大學出版社， 2011.

[2] 嚴蔚敏， 吳偉民. 數據結構（C語言版）[M] . 北京：清華大學出版社， 2002.

[3] 劉模群. 排序算法時間復雜度研究[J]. 軟件導刊， 2012（6）.

作者簡介

馮毅宏，女，講師， 主要從事非線性動力系統圖形化和計算機教育研究。