常見(jiàn)比較排序算法的比較

• 幾種常見(jiàn)的排序算法之比較

  排序的基本概念以及其算法的種類(lèi)，介紹幾種常見(jiàn)的排序算法的算法：冒泡排序、選擇排序、插入排序、歸并排序、快速排序、希爾排序的算法和分析它們各自的復(fù)雜度，然后以表格的形式，清晰直觀的表現(xiàn)出它們的復(fù)雜度的不同。在研究學(xué)習(xí)了之前幾種排序算法的基礎(chǔ)上，討論發(fā)現(xiàn)一種新的排序算法，并通過(guò)了進(jìn)一步的探索，找到了新的排序算法較之前幾種算法的優(yōu)勢(shì)與不足。

  排序算法，是計(jì)算機(jī)編程中的一個(gè)常見(jiàn)問(wèn)題。在日常的數(shù)據(jù)處理中，面對(duì)紛繁的數(shù)據(jù)，我們也許有成百上千種要求，因此只有當(dāng)數(shù)據(jù)經(jīng)過(guò)恰當(dāng)?shù)呐判蚝?，才能更符合用?hù)的要求。因此，在過(guò)去的數(shù)十載里，程序員們?yōu)槲覀兞粝铝藥追N經(jīng)典的排序算法，他們都是智慧的結(jié)晶。本文將帶領(lǐng)讀者探索這些有趣的排序算法，其中包括介紹排序算法的某些基本概念以及幾種常見(jiàn)算法，分析這些算法的時(shí)間復(fù)雜度，同時(shí)在最后將介紹我們獨(dú)創(chuàng)的一種排序方法，以供讀者參考評(píng)判。

• 幾種常見(jiàn)算法的介紹及復(fù)雜度分析

1.基本概念

1.1穩(wěn)定排序(stable sort)和非穩(wěn)定排序

  穩(wěn)定排序是所有相等的數(shù)經(jīng)過(guò)某種排序方法后，仍能保持它們?cè)谂判蛑暗南鄬?duì)次序，。反之，就是非穩(wěn)定的排序。

  比如：一組數(shù)排序前是a1,a2,a3,a4,a5，其中a2=a4，經(jīng)過(guò)某種排序后為a1,a2,a4,a3,a5，

則我們說(shuō)這種排序是穩(wěn)定的，因?yàn)閍2排序前在a4的前面，排序后它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩(wěn)定的了。

1.2內(nèi)排序( internal sorting )和外排序( external sorting)

  在排序過(guò)程中，所有需要排序的數(shù)都在內(nèi)存，并在內(nèi)存中調(diào)整它們的存儲(chǔ)順序，稱(chēng)為內(nèi)排序； 在排序過(guò)程中，只有部分?jǐn)?shù)被調(diào)入內(nèi)存，并借助內(nèi)存調(diào)整數(shù)在外存中的存放順序排序方法稱(chēng)為外排序。

1.3算法的時(shí)間復(fù)雜度和空間復(fù)雜度

所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。 一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。

2.幾種常見(jiàn)算法

2.1冒泡排序 （Bubble Sort）

  冒泡排序方法是最簡(jiǎn)單的排序方法。這種方法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對(duì)這個(gè)“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個(gè)序列，并時(shí)刻注意兩個(gè)相鄰的元素的順序是否正確。如果發(fā)現(xiàn)兩個(gè)相鄰元素的順序不對(duì)，即“輕”的元素在下面，就交換它們的位置。顯然，處理一遍之后，“最輕”的元素就浮到了最高位置；處理二遍之后，“次輕”的元素就浮到了次高位置。在作第二遍處理時(shí)，由于最高位置上的元素已是“最輕”元素，所以不必檢查。一般地，第i遍處理時(shí)，不必檢查第i高位置以上的元素，因?yàn)榻?jīng)過(guò)前面i-1遍的處理，它們已正確地排好序。

冒泡排序是穩(wěn)定的。算法時(shí)間復(fù)雜度是O(n ^2)。

2.2選擇排序 （Selection Sort）

  選擇排序的基本思想是對(duì)待排序的記錄序列進(jìn)行n-1遍的處理，第i遍處理是將L[i..n]中最小者與L[i]交換位置。這樣，經(jīng)過(guò)i遍處理之后，前i個(gè)記錄的位置已經(jīng)是正確的了。選擇排序是不穩(wěn)定的。算法復(fù)雜度是O(n ^2 )。

2.3插入排序 （Insertion Sort）

  插入排序的基本思想是，經(jīng)過(guò)i-1遍處理后,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當(dāng)位置，使得L[1..i]又是排好序的序列。要達(dá)到這個(gè)目的，我們可以用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤ L[i]，則L[1..i]已排好序，第i遍處理就結(jié)束了；否則交換L[i]與L[i-1]的位置，繼續(xù)比較L[i-1]和L[i-2]，直到找到某一個(gè)位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]時(shí)為止。圖1演示了對(duì)4個(gè)元素進(jìn)行插入排序的過(guò)程，共需要(a),(b),(c)三次插入。直接插入排序是穩(wěn)定的。算法時(shí)間復(fù)雜度是O(n ^2)

2.4堆排序

  堆排序是一種樹(shù)形選擇排序，在排序過(guò)程中，將A[n]看成是完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇最小的元素。堆排序是不穩(wěn)定的。算法時(shí)間復(fù)雜度O(nlog n)。

2.5歸并排序

  設(shè)有兩個(gè)有序（升序）序列存儲(chǔ)在同一數(shù)組中相鄰的位置上，不妨設(shè)為A[l..m]，A[m+1..h]，將它們歸并為一個(gè)有序數(shù)列，并存儲(chǔ)在A[l..h]。其時(shí)間復(fù)雜度無(wú)論是在最好情況下還是在最壞情況下均是O(nlog2n)。

2.6快速排序

  快速排序是對(duì)冒泡排序的一種本質(zhì)改進(jìn)。它的基本思想是通過(guò)一趟掃描后，使得排序序列的長(zhǎng)度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長(zhǎng)度可能只減少1。快速排序通過(guò)一趟掃描，就能確保某個(gè)數(shù)（以它為基準(zhǔn)點(diǎn)吧）的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止。快速排序是不穩(wěn)定的。最理想情況算法時(shí)間復(fù)雜度O(nlog2n)，最壞O(n ^2)。

2.7希爾排序

 在直接插入排序算法中，每次插入一個(gè)數(shù)，使有序序列只增加1個(gè)節(jié)點(diǎn)，并且對(duì)插入下一個(gè)數(shù)沒(méi)有提供任何幫助。如果比較相隔較遠(yuǎn)距離（稱(chēng)為 增量）的數(shù)，使得數(shù)移動(dòng)時(shí)能跨過(guò)多個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換。D.L.shell于1959年在以他名字命名的排序算法中實(shí)現(xiàn)了這一思想。算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。希爾排序是不穩(wěn)定的。算法時(shí)間復(fù)雜度是O(n2)。

• 各排序算法時(shí)間復(fù)雜度比較

寫(xiě)出下列算法的時(shí)間復(fù)雜度。

（1）冒泡排序；

（2）選擇排序；

（3）插入排序；

（4）快速排序；

（5）堆排序；

（6）歸并排序；

答案：

冒泡排序算法時(shí)間復(fù)雜度是O(n^2)。

選擇排序算法復(fù)雜度是O(n^2)。

插入排序算法時(shí)間復(fù)雜度是O(n^2)

快速排序快速排序是不穩(wěn)定的。最理想情況算法時(shí)間復(fù)雜度O(nlog2n)，最壞O(n^2)。

堆排序算法時(shí)間復(fù)雜度O(nlogn)。

歸并排序的時(shí)間復(fù)雜度是O(nlog2n)。

常用的排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度

排序法    最差時(shí)間分析 平均時(shí)間復(fù)雜度 穩(wěn)定度 空間復(fù)雜度

冒泡排序 O(n2)       O(n2)    穩(wěn)定  O(1)

快速排序 O(n2)      O(n*log2n) 不穩(wěn)定 O(log2n)~O(n)

選擇排序 O(n2)       O(n2)     穩(wěn)定  O(1)

二叉樹(shù)排序 O(n2)     O(n*log2n) 不一頂  O(n)

插入排序      O(n2)       O(n2)      穩(wěn)定  O(1)

堆排序     O(n*log2n) O(n*log2n) 不穩(wěn)定  O(1)

希爾排序 O        O       不穩(wěn)定 O(1)

1、時(shí)間復(fù)雜度 

（1）時(shí)間頻度一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度。記為T(mén)(n)。 

（2）時(shí)間復(fù)雜度在剛才提到的時(shí)間頻度中，n稱(chēng)為問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律。為此，我們引入時(shí)間復(fù)雜度概念。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí)，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱(chēng)f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=Ｏ(f(n)),稱(chēng)Ｏ(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。 

在各種不同算法中，若算法中語(yǔ)句執(zhí)行次數(shù)為一個(gè)常數(shù)，則時(shí)間復(fù)雜度為O(1),另外，在時(shí)間頻度不相同時(shí)，時(shí)間復(fù)雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時(shí)間復(fù)雜度相同，都為O(n2)。按數(shù)量級(jí)遞增排列，常見(jià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)。隨著問(wèn)題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。 2、空間復(fù)雜度與時(shí)間復(fù)雜度類(lèi)似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量。記作: S(n)=O(f(n)) 我們一般所討論的是除正常占用內(nèi)存開(kāi)銷(xiāo)外的輔助存儲(chǔ)單元規(guī)模。討論方法與時(shí)間復(fù)雜度類(lèi)似，不再贅述。 

（3）漸進(jìn)時(shí)間復(fù)雜度評(píng)價(jià)算法時(shí)間性能 　　主要用算法時(shí)間復(fù)雜度的數(shù)量級(jí)(即算法的漸近時(shí)間復(fù)雜度)評(píng)價(jià)一個(gè)算法的時(shí)間性能。

2、類(lèi)似于時(shí)間復(fù)雜度的討論，一個(gè)算法的空間復(fù)雜度(Space Complexity)S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它也是問(wèn)題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡(jiǎn)稱(chēng)為空間復(fù)雜度。 

空間復(fù)雜度(Space Complexity)是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度。一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間，算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)方面。算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間是由要解決的問(wèn)題決定的，是通過(guò)參數(shù)表由調(diào)用函數(shù)傳遞而來(lái)的，它不隨本算法的不同而改變。存儲(chǔ)算法本身所占用的存儲(chǔ)空間與算法書(shū)寫(xiě)的長(zhǎng)短成正比，要壓縮這方面的存儲(chǔ)空間，就必須編寫(xiě)出較短的算法。算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間隨算法的不同而異，有的算法只需要占用少量的臨時(shí)工作單元，而且不隨問(wèn)題規(guī)模的大小而改變，我們稱(chēng)這種算法是“就地/"進(jìn)行的，是節(jié)省存儲(chǔ)的算法，如這一節(jié)介紹過(guò)的幾個(gè)算法都是如此；有的算法需要占用的臨時(shí)工作單元數(shù)與解決問(wèn)題的規(guī)模n有關(guān)，它隨著n的增大而增大，當(dāng)n較大時(shí)，將占用較多的存儲(chǔ)單元，例如將在第九章介紹的快速排序和歸并排序算法就屬于這種情況。

如當(dāng)一個(gè)算法的空間復(fù)雜度為一個(gè)常量，即不隨被處理數(shù)據(jù)量n的大小而改變時(shí)，可表示為O(1)；當(dāng)一個(gè)算法的空間復(fù)雜度與以2為底的n的對(duì)數(shù)成正比時(shí)，可表示為0(10g2n)；當(dāng)一個(gè)算法的空I司復(fù)雜度與n成線性比例關(guān)系時(shí)，可表示為0(n).若形參為數(shù)組，則只需要為它分配一個(gè)存儲(chǔ)由實(shí)參傳送來(lái)的一個(gè)地址指針的空間，即一個(gè)機(jī)器字長(zhǎng)空間；若形參為引用方式，則也只需要為其分配存儲(chǔ)一個(gè)地址的空間，用它來(lái)存儲(chǔ)對(duì)應(yīng)實(shí)參變量的地址，以便由系統(tǒng)自動(dòng)引用實(shí)參變量。