吳偉娜　孫世鵬　楊風(fēng)　戴敏龍　張宏

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

關(guān)鍵詞：排序算法；時(shí)間復(fù)雜度；空間復(fù)雜度；算法實(shí)現(xiàn)

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）09-2146-03

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

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

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

1.1 排序的基本概念

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

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

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

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

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

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

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

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

sum=0； （1次）

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

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

sum++； （n2次）

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

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

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

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

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

2 排序算法的分析比較

2.1 插入排序

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

2.1.1 直接插入排序

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

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

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

2.1.2 希爾排序

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

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

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

2.2 選擇排序

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

2.2.1 直接選擇排序

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

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

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

2.2.2 堆排序

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

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

2.3 交換排序

基本思想：顧名思義，就是一組待排序的數(shù)據(jù)元素中，按照位置的先后順序相互比較各自的關(guān)鍵碼，如果是逆序，則交換這兩個(gè)數(shù)據(jù)元素，直到該序列數(shù)據(jù)元素有序?yàn)橹埂?/p>

2.3.1 冒泡排序

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

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

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

2.3.2 快速排序

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

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

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

2.4 歸并排序

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

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

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

2.5 基數(shù)排序

基數(shù)排序?qū)儆诜峙涫脚判?，其基本思想是：首先是低位排序，然后收集；其次是高位排序，然后再收集；依次類推，直到最高位?/p>

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

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

3 排序算法的選擇

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

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

[排序方法＼&時(shí)間復(fù)雜度＼&空間

復(fù)雜度＼&穩(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 結(jié)束語

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

參考文獻(xià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] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2007.

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