吳偉娜　孫世鵬　楊風　戴敏龍　張宏

摘要：排序是計算機領域的一種重要操作，實現(xiàn)方法有很多種。該文從算法的基本思想、時間復雜度、空間復雜度、穩(wěn)定性和問題的規(guī)模n值大小等方面對常用的排序算法進行了比較分析，為各種實際應用領域選擇、設計一個高效且合理實用的算法提供了依據(jù)。

關鍵詞：排序算法；時間復雜度；空間復雜度；算法實現(xiàn)

中圖分類號：TP312 文獻標識碼：A 文章編號：1009-3044（2013）09-2146-03

排序是計算機圖形學、計算機輔助設計、模式識別、商業(yè)事物處理和日常生活等領域的一種重要操作，應用廣泛[1]，比如招生切線的分數(shù)排序、錄取新生的成績排序等，是計算機科學中的需要解決的重要問題之一。計算機程序中的排序是將一串任意序列的數(shù)據(jù)按照所要求的既定排序方式確定每個數(shù)據(jù)的具體位置的算法。在以上領域的數(shù)據(jù)處理時，程序的排序算法占了很大的比重。因此，排序算法既有廣泛的應用價值，又有深刻的理論意義，曾經(jīng)被列為對科學與工程計算的研究影響最大的十大問題之一[2]，長期以來，人們?yōu)榱烁鞣N領域的應用需要，研究、開發(fā)出了多種排序算法，這些算法有著各自的特點，實現(xiàn)方法不盡相同、速度也有差異，而且都在各自的應用領域扮演了重要的角色。

盡管已經(jīng)開發(fā)出了各種不盡相同的排序算法，但是對排序算法的復雜度分析、算法的穩(wěn)定度和數(shù)據(jù)結構的研究是解決許多實際應用的基礎。該文從排序算法的基本概念、原理出發(fā)，分別從算法復雜度（時間、空間）、算法的穩(wěn)定性和速度等方面進行分析比較，為具體領域應用的排序選擇提供依據(jù)，使得執(zhí)行效率更高。

1 排序的基本概念和算法分析的理論依據(jù)

1.1 排序的基本概念

排序：將數(shù)據(jù)表中沒有規(guī)律、任意序列的數(shù)據(jù)元素按照既定的排序依據(jù)（關鍵碼）排列成有一定規(guī)律的序列。

關鍵碼：規(guī)定數(shù)據(jù)對象的其中一個屬性域用作排序依據(jù)，從而區(qū)分對象，該屬性域就是關鍵碼。當數(shù)據(jù)表中各對象的關鍵碼互不相同時，該關鍵碼為主關鍵碼；否則為次關鍵碼；根據(jù)主關鍵碼進行排序時，結果是唯一的，否者可能不唯一。

內部、外部排序：所謂內部排序是指排序時數(shù)據(jù)元素全部存放在j計算機的隨機存儲器（內存）；外部排序是指排序時數(shù)據(jù)元素在內、外存之間不斷移動（待排序的數(shù)據(jù)量很大，內存無法一次容納全部數(shù)據(jù)）。

靜態(tài)排序：所謂靜態(tài)排序是指對數(shù)據(jù)元素經(jīng)過比較和判斷之后將對象移動到相應的位置。

動態(tài)排序：所謂動態(tài)排序是指給每個對象增加一個鏈接指針，對數(shù)據(jù)元素經(jīng)過比較和判斷之后不移動對象，而是修改對象的鏈接指針來達到元素之間順序的改變。

1.2 算法分析的理論依據(jù)

一個問題可以采用不同算法來實現(xiàn)，算法的質量優(yōu)劣直接影響算法的效率。算法分析的目的在于選擇合適的算法和改進算法。評價一個算法的優(yōu)劣主要是根據(jù)算法的復雜度（分為時間復雜度和空間復雜度），不同的排序算法，其復雜度也不一樣，簡單的算法程序，其執(zhí)行效率也低；反之，復雜的算法程序，其執(zhí)行效率相對來說也會比較高。

如果一個問題的規(guī)模是n，解這一問題的某一算法所需要的時間為T（n），它是n的某一函數(shù)，T（n）稱為這一算法的時間復雜度。當問題規(guī)模n趨于無窮大時，如果存在某個輔助函數(shù)f（n），T（n）/f（n）的極限值為不等于零的常數(shù)，該時間復雜性的極限情形稱為算法的漸近時間復雜度[3-4]，記作O（f（n））。一般情況，在算法分析時對兩者不予區(qū)分，經(jīng)常是將漸近時間復雜度T（n）=O（f（n））簡稱為時間復雜度，f（n）是算法中頻度最大的語句頻度。常見的時間復雜度有：常數(shù)階O（1），對數(shù)階O（log2n），線性階O（n），線性對數(shù)階O（nlog2n），平方階O（n2），立方階O（n3），k次方階O（nk），指數(shù)階O（2n）。n越大，時間復雜度也越大，算法的執(zhí)行效率就越低。例如：

sum=0； （1次）

for（i=1；i<=n；i++） （n次）

for（j=1；j<=n；j++） （n2次）

sum++； （n2次）

在上述交換i和j的算法中，時間復雜度為T（n）=2n2+n+1 =O（n2）。

空間復雜度是指算法在執(zhí)行過程中，根據(jù)n的規(guī)模大小需要臨時占用的存儲空間[3-4]，和時間復雜度類似，也是問題規(guī)模n的函數(shù)，記作S（n）=O（f（n））。

一般情況，時間復雜度和空間復雜度是相互影響的，即：時間復雜度較好時（效率較高），空間復雜度的可能就變差（占用較多的存儲空間），反之也一樣。所以設計或選擇一個好的算法時要考慮算法的時間復雜度和空間復雜度。

對于排序算法的穩(wěn)定性，如果待排序的序列中存在兩個或兩個以上具有相同關鍵詞的數(shù)據(jù)，排序后這些數(shù)據(jù)的相對次序保持不變，即它們的位置保持不變，則該算法是穩(wěn)定的；如果排序后，數(shù)據(jù)的相對次序發(fā)生了變化，則該算法是不穩(wěn)定的。

不僅僅是時間復雜度和空間復雜度之間相互影響，算法的所有性能之間或多或少都會相互影響。因此，當設計或選擇一個算法時，尤其是大型算法，要綜合考慮算法的各項性能：復雜度、穩(wěn)定性、以及算法描述語言的特性，算法運行的機器系統(tǒng)環(huán)境等各方面因素。

2 排序算法的分析比較

2.1 插入排序

基本思想：每次將一個待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當位置，使數(shù)據(jù)元素依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。關鍵在于將新的數(shù)據(jù)元素插入到已排序好的序列當中，包括找到應插入的位置、如何移動序列當中的數(shù)據(jù)元素。因此，插入排序又分為以下兩種。

2.1.1 直接插入排序

基本思想：將欲插入的第i個數(shù)據(jù)元素的關鍵碼與前面已經(jīng)排序好的i-1、i-2、i-3、…數(shù)據(jù)元素的關鍵碼進行順序比較，通過這種線性搜索的方法找到第i個數(shù)據(jù)元素的插入位置，并且原來位置的數(shù)據(jù)元素順序后移，直到全部排好順序。

直接插入排序中，關鍵詞相同的數(shù)據(jù)元素將保持原有位置不變，所以該算法是穩(wěn)定的，時間復雜度的最壞值為平方階O（n2），空間復雜度為常數(shù)階O（1）。

該排序方法是對冒泡排序的改進，比冒泡排序大約快3倍，但是只適用于數(shù)據(jù)量較小（1000）的排序。

2.1.2 希爾排序

基本思想：根據(jù)不同步長對數(shù)據(jù)元素執(zhí)行插入排序，剛開始數(shù)據(jù)非常無序時，步長最大，此時插入排序的元素個數(shù)很少，速度很快；數(shù)據(jù)基本有序時，步長很小，插入排序對于有序的序列效率很高。因此，如果元素為你的待排序序列，先取一個小于n的整數(shù)I作為步長，將所有元素分為I個子序列，在每個子序列中分別執(zhí)行直接插入排序。然后縮小步長I重新劃分子序列和排序，直到I=1，此時，相當于將所有元素放在一個序列當中。

剛開始，由于步長I很大，所以排序效率很高，當步長I逐漸減小時，序列也趨于有序化，所以排序效率也很高。因此，希爾排序時間復雜度會比O（n2）好一些，然而，多次插入排序中，第一次插入排序是穩(wěn)定的，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，所以希爾排序是不穩(wěn)定的。

相對來說，希爾排序比較簡單，適用于小數(shù)據(jù)量（5000以下）的排序，比直接插入排序快2倍、比冒泡排序快5倍，因此，希爾排序適用于小數(shù)據(jù)量的、排序速度要求不高的排序。

2.2 選擇排序

基本思想：每一趟掃描時，從待排序的數(shù)據(jù)元素中選出關鍵碼最小或最大的一個元素，順序放在已經(jīng)排好順序序列的最后，直到全部待排序的數(shù)據(jù)元素排完為止。

2.2.1 直接選擇排序

基本思想：給每個位置選擇關鍵碼最小的數(shù)據(jù)元素，即：選擇最小的元素與第一個位置的元素交換，然后在剩下的元素中再選擇最小的與第二個位置的元素交換，直到倒數(shù)第二個元素和最后一個元素比較為止。

根據(jù)其基本思想，每當掃描一趟時，如果當前元素比一個元素小，而且這個小元素又出現(xiàn)在一個和當前元素相等的元素后面，則它們的位置發(fā)生了交換，所以直接選擇排序時不穩(wěn)定的，其時間復雜度為平方階O（n2），空間復雜度為O（1）。

該算法和冒泡排序算法一樣，適用于n值較小的場合，而且是排序算法發(fā)展的初級階段，在實際應用中采用的幾率較小。

2.2.2 堆排序

堆排序時對直接選擇排序的一種有效改進，其基本思想是：將所有的數(shù)據(jù)建成一個堆，最大的數(shù)據(jù)在堆頂，然后將堆頂?shù)臄?shù)據(jù)元素和序列的最后一個元素交換；接著重建堆、交換數(shù)據(jù)，依次下去，從而實現(xiàn)對所有的數(shù)據(jù)元素的排序。完成堆排序需要執(zhí)行兩個動作：建堆和堆的調整，如此反復進行。

由基本思想可知，堆排序有可能會使得兩個相同關鍵碼的元素位置發(fā)生互換，所以是不穩(wěn)定的，其平均時間復雜度為O（nlog2n），空間復雜度為O（1）。由于堆的不斷建立和調整，所以堆排序不適用于數(shù)據(jù)元素較少的排序，但是對于n較大的情形，該算法能夠表現(xiàn)出較大的優(yōu)越性。因此，堆排序比較適用于數(shù)據(jù)量達到百萬及其以上的排序，在這種情況下，使用遞歸設計的快速排序和歸并排序可能會發(fā)生堆棧溢出的現(xiàn)象。

2.3 交換排序

基本思想：顧名思義，就是一組待排序的數(shù)據(jù)元素中，按照位置的先后順序相互比較各自的關鍵碼，如果是逆序，則交換這兩個數(shù)據(jù)元素，直到該序列數(shù)據(jù)元素有序為止。

2.3.1 冒泡排序

基本思想：對于待排序的一組數(shù)據(jù)元素，把每個數(shù)據(jù)元素看作有重量的氣泡，按照輕氣泡不能在重氣泡之下的原則，將未排好順序的全部元素自上而下的對相鄰兩個元素依次進行比較和調整，讓較重的元素往下沉，較輕的往上冒。

根據(jù)基本思想，只有在兩個元素的順序與排序要求相反時才將調換它們的位置，否則保持不變，所以冒泡排序時穩(wěn)定的。時間復雜度為平方階O（n2），空間復雜度為O（1）。

冒泡排序時最慢的排序算法，是排序算法發(fā)展的初級階段，實際應用中采用該算法的幾率比較小。

2.3.2 快速排序

快速排序是對冒泡排序本質上的改進。其基本思想為：是一個就地排序，分而治之，大規(guī)模遞歸的算法。即：通過一趟掃描后確保基準點的這個數(shù)據(jù)元素的左邊元素都比它小、右邊元素都比它大，接著又以遞歸方法處理左右兩邊的元素，直到基準點的左右只有一個元素為止。

快速排序時一個不穩(wěn)定的算法，其最壞值的時間復雜度為平方階O（n2），空間復雜度為O（log n）。

快速排序是遞歸的、速度最快的排序算法，但是在內存有限的情況下不是一個好的選擇；而且，對于基本有序的數(shù)據(jù)序列排序，快速排序反而變得比較慢。

2.4 歸并排序

歸并排序的基本思想是：把數(shù)據(jù)序列遞歸地分成短序列，即把1分成2、2分成4、依次分解，當分解到只有1個一組的時候排序這些分組，然后依次合并回原來的序列，不斷合并直到原序列全部排好順序。

合并過程中可以確保兩個相等的當前元素中，把處在前面的元素保存在結果序列的前面，因此歸并排序是穩(wěn)定的，其時間復雜度為O（nlog2n），空間復雜度為O（n）。

歸并排序比堆排序要快，但是需要的存儲空間增加一倍。

2.5 基數(shù)排序

基數(shù)排序屬于分配式排序，其基本思想是：首先是低位排序，然后收集；其次是高位排序，然后再收集；依次類推，直到最高位。

基數(shù)排序基于分別排序、分別收集，是穩(wěn)定的排序算法，其時間復雜度為O（nlog（r）d），r是采取的基數(shù)、d是堆數(shù)，空間復雜度為O（rd）。

基數(shù)排序適用于規(guī)模n值很大的場合，但是只適用于整數(shù)的排序，如果對浮點數(shù)進行基數(shù)排序，則必須明確浮點數(shù)的存儲格式，然后通過某種方式將其映射到整數(shù)上，最后再映射回去，過程復雜。

3 排序算法的選擇

經(jīng)過排序算法的分析比較，各種算法有自己比較適合的應用場合，選擇算法時應綜合考慮穩(wěn)定性、時間復雜度和空間復雜度等因素。綜合前面的分析比較，各種算法的各種因素影響見表1。

表1 排序算法的分析與比較

[排序方法＼&時間復雜度＼&空間

復雜度＼&穩(wěn)定性＼&規(guī)模n＼&平均情況＼&最壞情況＼&插入排序＼&直接插入排序＼&O（n2）＼&O（n2）＼&O（1）＼&是＼&n?。?希爾排序＼&O（nlog2n）＼&O（nlog2n）＼&O（1）＼&否＼&n小＼&選擇排序＼&直接選擇排序＼&O（n2）＼&O（n2）＼&O（1）＼&否＼&n?。?堆排序＼&O（nlog2n）＼&O（nlog2n）＼&O（1）＼&否＼&n大＼&交換排序＼&冒泡排序＼&O（nlog2n）＼&O（n2）＼&O（log n）＼&是＼&n?。?快速排序＼&O（knlog2n）＼&O（n2）＼&O（log n）＼&否＼&n大＼&歸并排序＼&O（nlog2n）＼&O（nlog2n）＼&O（n）＼&是＼&n大＼&基數(shù)排序＼&O（nlog（r）d）＼&O（nlog（r）d）＼&O（rd）＼&是＼&n大＼&]

4 結束語

排序算法的應用非常廣泛，是計算機圖形學、計算機輔助設計、模式識別、商業(yè)事物處理和日常生活等領域的一種重要的程序操作。該文從時間復雜度、空間復雜度、穩(wěn)定性以及規(guī)模n值的大小等方面對常用的排序算法進行了分析比較和總結，為排序算法的選擇提供了依據(jù)。規(guī)模n值較小時、且對穩(wěn)定性不作要求時選用選擇排序比較有利，對穩(wěn)定性有要求時選用插入或冒泡排序比較有利。規(guī)模n值較大、且關鍵碼元素隨機、對穩(wěn)定性沒要求時選用快速排序比較有利；關鍵碼元素有序、對穩(wěn)定性有要求時，存儲空間又允許的情況下選用歸并排序比較有利；關鍵碼元素有序、對穩(wěn)定性沒有要求時選用堆排序比較有利?？偠灾?，充分了解各種排序算法自身的特點及其基本思想在選擇、設計高效且合理的算法具有重要意義。

參考文獻：

[1] Cormen T H，Leiserson C E，Rivest R L，et al.Introduction to Algorithms[M].2nd ed.The MIT Press，2001.

[2] Dongarra J.The top 10 algorithms[J].IEEE Computing in Science & Engineering，2000，2（1）： 22-23.

[3] 嚴蔚敏，吳偉民.數(shù)據(jù)結構[M].北京：清華大學出版社，2007.

[4] 王曉東，傅清祥，葉東毅.算法與數(shù)據(jù)結構[M].北京：電子工業(yè)出版社，1998.