常用內排序算法的分析與比較

摘要：該文在對常用內排序算法基本思想分析的基礎上，從算法的穩定性；算法在最好情況下、最壞情況下的交換次數和移動次數；算法的時間復雜度等方面進行了詳細的比較分析。

關鍵詞：排序算法；分析；比較

中圖分類號：TP312文獻標識碼：A文章編號：1009-3044(2008)29-0382-04

The Commonly Used in Sort Algorithm's Analysis and Compares

BAI Hong-yi

(Ningxia Traffic School，Ningxia 750001，China)

Abstract: This article to commonly used in sort algorithm basic philosophy analysis foundation， from algorithm stability; Algorithm in the best situation， in worst situation exchange number of times and motion number of times.Algorithm aspects and so on time order of complexity have carried on the detailed comparison and analysis.

Key words: sort algorithm; analysis; compare

1 排序的基本概念

排序：將數據表（datalist）中無規律數據按關鍵碼在一定的規律順次下排列起來。

關鍵碼（key）：通常數據對象有多個屬性域，即多個數據成員組成，其中有一個屬性域可用來區分對象，作為排序依據。該域即為關鍵碼。每個數據表用哪個屬性域作為關鍵碼，要視具體的應用需要而定。即使是同一個表，在解決不同問題的場合也可能取不同的域做關鍵碼。

主關鍵碼：如果在數據表中各個對象的關鍵碼互不相同，這種關鍵碼即主關鍵碼。按照主關鍵碼進行排序，排序的結果是唯一的。

次關鍵碼：數據表中有些對象的關鍵碼可能相同，這種關鍵碼稱為次關鍵碼。按照次關鍵碼進行排序，排序的結果可能不唯一。

排序算法的穩定性：如果在對象序列中有兩個對象r[i]和r[j]，它們的關鍵碼k[i] = k[j]，且在排序之前，對象r[i]排在r[j]前面。如果在排序之后，對象r[i]仍在對象r[j]的前面，則稱這個排序方法是穩定的，否則稱這個排序方法是不穩定的。

內排序與外排序：內排序是指在排序期間數據對象全部存放在內存的排序；外排序是指在排序期間全部對象個數太多，不能同時存放在內存，必須根據排序過程的要求，不斷在內、外存之間移動的排序。

排序的時間開銷：排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷可用算法執行中的數據比較次數與數據移動次數來衡量。本文給出算法運行時間代價的大略估算一般都按平均情況進行估算。對于那些受對象關鍵碼序列初始排列及對象個數影響較大的，需要按最好情況和最壞情況進行估算。

靜態排序：排序的過程是對數據對象本身進行物理地重排，經過比較和判斷，將對象移到合適的位置。這時，數據對象一般都存放在一個順序的表中。

動態排序：給每個對象增加一個鏈接指針，在排序的過程中不移動對象或傳送數據，僅通過修改鏈接指針來改變對象之間的邏輯順序，從而達到排序的目的。

2 插入排序（Insert Sorting）

插入排序的基本方法是：每步將一個待排序的對象，按其關鍵碼大小，插入到前面已經排好序的一組對象的適當位置上，直到對象全部插入為止。

2.1 直接插入排序（Insert Sort）

直接插入排序的基本思想是：當插入第i (i≥1) 個對象時，前面的v[0]， v[1]， …， v[i-1]已經排好序。這時，用v[i]的關鍵碼與v[i-1]， v[i-2]， …的關鍵碼順序進行比較，找到插入位置即將v[i]插入，原來位置上的對象向后順移。

算法分析：

若設待排序的對象個數為curremtsize = n，則該算法的主程序執行n-1趟。

關鍵碼比較次數和對象移動次數與對象關鍵碼的初始排列有關。

最好情況下，排序前對象已經按關鍵碼大小從小到大有序，每趟只需與前面的有序對象序列的最后一個對象的關鍵碼比較 1 次，移動2次對象，總的關鍵碼比較次數為 n-1，對象移動次數為 2(n-1)。

最壞情況下，第i趟時第i個對象必須與前面i -1個對象都做關鍵碼比較，并且每做 1 次比較就要做 1 次數據移動。則總的關鍵碼比較次數KCN和對象移動次數RMN分別為：

若待排序對象序列中出現各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關鍵碼比較次數和對象移動次數約為n2/4。因此，直接插入排序的時間復雜度為O(n2)。

直接插入排序是一種穩定的排序方法。

2.2 折半插入排序（Binary Insertsort）

折半插入排序基本思想是：設在順序表中有一個對象序列V[0]， V[1]， …， v[n-1]。其中，v[0]， V[1]， …， v[i-1]是已經排好序的對象。在插入v[i]時，利用折半搜索法尋找v[i]的插入位置。

算法分析：

折半查找比順序查找快，所以折半插入排序就平均性能要比直接插入排序要快。

當n較大時，總關鍵碼比較次數比直接插入排序的最壞情況要好得多，但比其最好情況要差。

在對象的初始排列已經按關鍵碼排好序或接近有序時，直接插入排序比折半插入排序執行的關鍵碼比較次數要少。折半插入排序的對象移動次數與直接插入排序相同，依賴于對象的初始排列。

對分插入排序是一個穩定的排序方法。

2.3 希爾排序（Shell Sort）

開始時gap的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，gap 值逐漸變小，子序列中對象個數逐漸變多，由于前面工作的基礎，大多數對象已基本有序，所以排序速度仍然很快。

算法分析：對特定的待排序對象序列，可以準確地估算關鍵碼的比較次數和對象移動次數。

但想要弄清關鍵碼比較次數和對象移動次數與增量選擇之間的依賴關系，并給出完整的數學分析，還沒有人能夠做到。Knuth利用大量的實驗統計資料得出，當n很大時，關鍵碼平均比較次數和對象平均移動次數大約在n1.25到1.6n1.25的范圍內。這是在利用直接插入排序作為子序列排序方法的情況下得到的。

3 交換排序（Exchange Sort）

交換排序的基本思想是兩兩比較待排序對象的關鍵碼，如果發生逆序，則交換之，直到所有對象都排好序為止。

3.1 起泡排序（Bubble Sort）

起泡排序的基本方法是：設待排序對象序列中的對象個數為 n。最多作 n-1 趟，i = 1， 2， …， n-2。在第 i 趟中順次兩兩比較v[n-j-1].Key和v[n-j].Key，j = n-1， n-2， …，i。如果發生逆序，則交換v[n -j-1]和v[n-j]。

第 i 趟對待排序對象序列v[i-1]， v[i]， …， v[n-1]進行排序，結果將該序列中關鍵碼最小的對象交換到序列的第一個位置(i-1)，其它對象也都向排序的最終位置移動。

當然在個別情形下，對象有可能在排序中途向相反的方向移動。

這樣最多做n-1趟起泡就能把所有對象排好序。

算法分析：在對象的初始排列已經按關鍵碼從小到大排好序時，此算法只執行一趟起泡，做n-1次關鍵碼比較，不移動對象。這是最好的情形。最壞的情形是算法執行了n-1趟起泡，第i趟 (1≤i< n) 做了n-i次關鍵碼比較，執行了n-i次對象交換。這樣在最壞情形下總的關鍵碼比較次數KCN和對象移動次數RMN為：

起泡排序需要一個附加對象以實現對象值的對換。

起泡排序是一個穩定的排序方法。

3.2 快速排序（Quick Sort）

快速排序方法的基本思想是任取待排序對象序列中的某個對象 (例如取第一個對象) 作為基準，按照該對象的關鍵碼大小，將整個對象序列劃分為左右兩個子序列： 左側子序列中所有對象的關鍵碼都小于或等于基準對象的關鍵碼，右側子序列中所有對象的關鍵碼都大于基準對象的關鍵碼，基準對象則排在這兩個子序列中間(這也是該對象最終應安放的位置)。然后分別對這兩個子序列重復施行上述方法，直到所有的對象都排在相應位置上為止。算法quicksort是一個遞歸的算法。

算法分析：

從快速排序算法的遞歸樹可知，快速排序的趟數取決于遞歸樹的深度。

如果每次劃分對一個對象定位后，該對象的左側子序列與右側子序列的長度相同，則下一步將是對兩個長度減半的子序列進行排序，這是最理想的情況。

在n個元素的序列中，對一個對象定位所需時間為 O(n)。若設 t(n) 是對 n 個元素的序列進行排序所需的時間，而且每次對一個對象正確定位后，正好把序列劃分為長度相等的兩個子序列，此時，總的計算時間為：

T(n) ≤ cn + 2 t(n/2 ) // c是一個常數

≤ Cn + 2 ( cn/2 + 2t(n/4) ) = 2cn + 4t(n/4)

≤ 2cn + 4 ( cn/4 +2t(n/8) ) = 3cn + 8t(n/8)

………

≤ Cn log2n + nt(1) = O(n log2n )

可以證明，函數quicksort的平均計算時間也是O(nlog2n)。實驗結果表明：就平均計算時間而言，快速排序是我們所討論的所有內排序方法中最好的一個。

快速排序是遞歸的，需要有一個棧存放每層遞歸調用時的指針和參數。

在最壞的情況，即待排序對象序列已經按其關鍵碼從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個比上一次少一個對象的子序列。這樣，必須經過n-1趟才能把所有對象定位，而且第i趟需要經過n-i次關鍵碼比較才能找到第i個對象的安放位置，總的關鍵碼比較次數將達到：

其排序速度退化到簡單排序的水平，比直接插入排序還慢。占用附加存儲（即棧）將達到O(n)。

若能更合理地選擇基準對象，使得每次劃分所得的兩個子序列中的對象個數盡可能地接近，可以加速排序速度，但是由于對象的初始排列次序是隨機的，這個要求很難辦到。

有一種改進辦法：取每個待排序對象序列的第一個對象、最后一個對象和位置接近正中的3個對象，取其關鍵碼居中者作為基準對象。

快速排序是一種不穩定的排序方法。

對于 n 較大的平均情況而言，快速排序是“快速”的，但是當 n 很小時，這種排序方法往往比其它簡單排序方法還要慢。

4 選擇排序

選擇排序的基本思想是：每一趟（例如第i趟，i = 0， 1， …， n-2）在后面n-i個待排序對象中選出關鍵碼最小的對象， 作為有序對象序列的第i個對象。待到第n-2趟作完，待排序對象只剩下1個，就不用再選了。

4.1 直接選擇排序（Select Sort）

直接選擇排序是一種簡單的排序方法，它的基本步驟是： 在一組對象v[i]～v[n-1]中選擇具有最小關鍵碼的對象；若它不是這組對象中的第一個對象，則將它與這組對象中的第一個對象對調； 在這組對象中剔除這個具有最小關鍵碼的對象，在剩下的對象v[i+1]～v[n-1]中重復執行，直到剩余對象只有一個為止。

算法分析：直接選擇排序的關鍵碼比較次數KCN與對象的初始排列無關。第 i 趟選擇具有最小關鍵碼對象所需的比較次數總是 n-i-1 次，此處假定整個待排序對象序列有 n 個對象。因此，總的關鍵碼比較次數為：

對象的移動次數與對象序列的初始排列有關。當這組對象的初始狀態是按其關鍵碼從小到大有序的時候，對象的移動次數RMN = 0，達到最少。

最壞情況是每一趟都要進行交換，總的對象移動次數為RMN = 3(n-1)。

直接選擇排序是一種不穩定的排序方法。

4.2 錦標賽排序（Tournament Tree Sort）

算法分析：

所以錦標賽排序總的時間復雜度為O(nlog2n)。如果有n個對象，必須使用至少2n-1 個結點來存放勝者樹。(n+n/2+4/n+…+1=2n-1)

Sn=(a1-an*q)/(1-q)

錦標賽排序是一個穩定的排序方法。

4.3 堆排序（Heap Sort）

利用堆及其運算，可以很容易地實現選擇排序的思路。

堆排序分為兩個步驟：第一步，根據初始輸入數據，利用堆的調整算法 FilterDown( ) 形成初始堆，第二步，通過一系列的對象交換和重新調整堆進行排序。最大堆的第一個對象V[0]具有最大的關鍵碼，將V[0]與V[n]對調，把具有最大關鍵碼的對象交換到最后，再對前面的n-1個對象，使用堆的調整算法FilterDown(0， n-1)，重新建立最大堆。結果具有次最大關鍵碼的對象又上浮到堆頂，即V[0]位置。再對調V[0]和V[n-1]，調用FilterDown(0， n-2)，對前n-2個對象重新調整，…。如此反復執行，最后得到全部排序好的對象序列。

算法分析：

堆排序是一個不穩定的排序方法。

5 小結

通過對常用排序算法的分析，下面對算法的穩定性；算法在最好情況下、最壞情況下的交換次數和移動次數；算法的時間復雜度進行綜合小結（表1）。

參考文獻：

[1] 克努 D E.計算機程序設計技巧3[M].管紀文，譯.北京:國防工業出版社，1999:185-190.

[2] 許卓群.數據結構[M].北京:高等教育出版社，1993:103-108.

[3] 嚴蔚敏.數據結構[M].北京:清華大學出版社，2004:207-215.