常見比較排序算法的比較

• 幾種常見的排序算法之比較

  排序的基本概念以及其算法的種類，介紹幾種常見的排序算法的算法：冒泡排序、選擇排序、插入排序、歸并排序、快速排序、希爾排序的算法和分析它們各自的復雜度，然后以表格的形式，清晰直觀的表現出它們的復雜度的不同。在研究學習了之前幾種排序算法的基礎上，討論發現一種新的排序算法，并通過了進一步的探索，找到了新的排序算法較之前幾種算法的優勢與不足。

  排序算法，是計算機編程中的一個常見問題。在日常的數據處理中，面對紛繁的數據，我們也許有成百上千種要求，因此只有當數據經過恰當的排序后，才能更符合用戶的要求。因此，在過去的數十載里，程序員們為我們留下了幾種經典的排序算法，他們都是智慧的結晶。本文將帶領讀者探索這些有趣的排序算法，其中包括介紹排序算法的某些基本概念以及幾種常見算法，分析這些算法的時間復雜度，同時在最后將介紹我們獨創的一種排序方法，以供讀者參考評判。

• 幾種常見算法的介紹及復雜度分析

1.基本概念

1.1穩定排序(stable sort)和非穩定排序

  穩定排序是所有相等的數經過某種排序方法后，仍能保持它們在排序之前的相對次序，。反之，就是非穩定的排序。

  比如：一組數排序前是a1,a2,a3,a4,a5，其中a2=a4，經過某種排序后為a1,a2,a4,a3,a5，

則我們說這種排序是穩定的，因為a2排序前在a4的前面，排序后它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩定的了。

1.2內排序( internal sorting )和外排序( external sorting)

  在排序過程中，所有需要排序的數都在內存，并在內存中調整它們的存儲順序，稱為內排序； 在排序過程中，只有部分數被調入內存，并借助內存調整數在外存中的存放順序排序方法稱為外排序。

1.3算法的時間復雜度和空間復雜度

所謂算法的時間復雜度，是指執行算法所需要的計算工作量。 一個算法的空間復雜度，一般是指執行這個算法所需要的內存空間。

2.幾種常見算法

2.1冒泡排序 （Bubble Sort）

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

冒泡排序是穩定的。算法時間復雜度是O(n ^2)。

2.2選擇排序 （Selection Sort）

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

2.3插入排序 （Insertion Sort）

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

2.4堆排序

  堆排序是一種樹形選擇排序，在排序過程中，將A[n]看成是完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。堆排序是不穩定的。算法時間復雜度O(nlog n)。

2.5歸并排序

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

2.6快速排序

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

2.7希爾排序

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

• 各排序算法時間復雜度比較

寫出下列算法的時間復雜度。

（1）冒泡排序；

（2）選擇排序；

（3）插入排序；

（4）快速排序；

（5）堆排序；

（6）歸并排序；

答案：

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

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

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

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

堆排序算法時間復雜度O(nlogn)。

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

常用的排序算法的時間復雜度和空間復雜度

排序法    最差時間分析 平均時間復雜度 穩定度 空間復雜度

冒泡排序 O(n2)       O(n2)    穩定  O(1)

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

選擇排序 O(n2)       O(n2)     穩定  O(1)

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

插入排序      O(n2)       O(n2)      穩定  O(1)

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

希爾排序 O        O       不穩定 O(1)

1、時間復雜度 

（1）時間頻度一個算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。 

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

在各種不同算法中，若算法中語句執行次數為一個常數，則時間復雜度為O(1),另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n2)。按數量級遞增排列，常見的時間復雜度有：常數階O(1),對數階O(log2n),線性階O(n), 線性對數階O(nlog2n),平方階O(n2)，立方階O(n3),...， k次方階O(nk),指數階O(2n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，算法的執行效率越低。 2、空間復雜度與時間復雜度類似，空間復雜度是指算法在計算機內執行時所需存儲空間的度量。記作: S(n)=O(f(n)) 我們一般所討論的是除正常占用內存開銷外的輔助存儲單元規模。討論方法與時間復雜度類似，不再贅述。 

（3）漸進時間復雜度評價算法時間性能 　　主要用算法時間復雜度的數量級(即算法的漸近時間復雜度)評價一個算法的時間性能。

2、類似于時間復雜度的討論，一個算法的空間復雜度(Space Complexity)S(n)定義為該算法所耗費的存儲空間，它也是問題規模n的函數。漸近空間復雜度也常常簡稱為空間復雜度。 

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

如當一個算法的空間復雜度為一個常量，即不隨被處理數據量n的大小而改變時，可表示為O(1)；當一個算法的空間復雜度與以2為底的n的對數成正比時，可表示為0(10g2n)；當一個算法的空I司復雜度與n成線性比例關系時，可表示為0(n).若形參為數組，則只需要為它分配一個存儲由實參傳送來的一個地址指針的空間，即一個機器字長空間；若形參為引用方式，則也只需要為其分配存儲一個地址的空間，用它來存儲對應實參變量的地址，以便由系統自動引用實參變量。