常見的排序算法簡介

排序的穩(wěn)定性

因為待排序的記錄序列中可能存在兩個或兩個以上的關鍵字相等的記錄， 排序結果可能會存在不唯一的情況。所以就有穩(wěn)定與不穩(wěn)定的定義。

假設ki=kj( 1 =< i <= n,1 =< j <= n, i != j)，且在排序前的序列中ri領先于rj。如果排序后ri仍領先于rj，則稱所用的排序方法是穩(wěn)定的;反之，若可能使得排序后的序列中rj領先于ri，則稱所用的排序方法是不穩(wěn)定的。

只要有一組關鍵字發(fā)生類似情況，就可認為此排序方法是不穩(wěn)定的。

內排序和外排序

根據(jù)在排序過程中待排序記錄是否全部放在內存中，排序分為內排序和外排序。

內排序是在排序整個過程中，待排序的所有記錄全部被放置在內存中。

外排序是由于排序的記錄個數(shù)太多，不能同時放置在內存中，整個排序過程需要在內外存之間多次交換數(shù)據(jù)才能進行。

對內排序來說，排序算法的性能主要有3個影響因素：

1、時間性能

排序算法的時間開銷是衡量其好壞的最重要的標志。

在內排序中，主要進行兩種操作：比較和移動。

高效率的內排序算法應該具有盡可能少的關鍵字比較次數(shù)和盡可能少的記錄移動次數(shù)。

2、輔助空間

評估算法的另一個主要標準是執(zhí)行算法所需要的輔助存儲空間。

輔助存儲空間是除了存放待排序所占用的存儲空間外，執(zhí)行算法所需要的其他存儲空間。

3、算法的復雜性

指算法本身的復雜性，過于復雜的算法也會影響排序的性能。

接下來本文介紹各種排序算法。

1. 冒泡排序Bubble Sort

冒泡排序是一種交換排序，它的基本思想是：

兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止。

算法復雜度分析：

使用優(yōu)化后的冒泡排序，最好的情況下，僅需要n - 1次比較，時間復雜度為O(n);最壞情況下，需要n(n - 1)/2次比較和交換;

所以平均時間復雜度為O(n2)。

2. 簡單選擇排序Simple Selection Sort

選擇排序的基本思想：

每一次遍歷時選取關鍵字最小的記錄作為有序序列的第i個記錄。

算法復雜度分析

簡單選擇排序最大的特點就是交換移動數(shù)據(jù)次數(shù)少，但它的比較次數(shù)是和數(shù)組本身是否有序是無關的，即無論最好最差的情況，都要進行n(n-1)/2次比較;在最好的情況下，不需要進行交換，在最壞的情況下，進行n-1次交換。

所以平均時間復雜度為O(n2)。

3. 直接插入排序Straight Insertion Sort

直接插入排序的基本操作：

將一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄遞增1的有序表。

插入排序是進行值移動，而是不值交換。所以在量較小的情況下插入排序性能要優(yōu)于冒泡和簡單選擇排序。

算法復雜度分析：

在最好的情況下，只需進行比較n - 1次，無需進行移動;

在最壞的情況下，比較(n + 2)(n - 1)/2次，交換(n + 4)(n - 1)/2次。

所以平均時間復雜度O(n2)

4. 二分插入排序Binary Insert Sort

二分(折半)插入排序是一種在直接插入排序算法上進行小改動的排序算法。其與直接排序算法最大的區(qū)別在于查找插入位置時使用的是二分查找的方式，在速度上有一定提升。

算法復雜度分析：

插入每個記錄需要O(log i)比較，最多移動i+1次，最少2次。最佳情況O(n log n)，最差和平均情況O(n^2)。

總排序碼比較次數(shù)比直接插入排序的最差情況好得多，但比最好情況要差，所元素初始序列已經按排序碼接近有序時，直接插入排序比二分插入排序比較次數(shù)少

5. 希爾排序Shell Sort

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。

希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然后算法再取越來越小的步長進行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數(shù)據(jù)幾乎是已排好的了。

更好的理解方式

將數(shù)組列在一個表中并對行排序(用插入排序)。重復這過程，不過每次用更小的列來進行。最后整個表就只有一列了。

將數(shù)組轉換至表是為了更好地理解這算法，算法本身僅僅對原數(shù)組進行排序(通過增加索引的步長，例如是用i += step_size而不是i++)。

比如第一次放在5列中對每行使用快速排序排序，第二次放在3列中，最后放在1列中。類比于步長從5到3再到1。

算法復雜度分析

希爾排序的算法復雜度和增量序列有關，只要最終步長為1任何步長序列都可以工作?？梢詤⒓酉柵判颉?/p>

6. 堆排序Heap Sort

堆

堆是具有下列性質的完全二叉樹：

每個節(jié)點的值都大于或等于其左右孩子節(jié)點的值，成為大頂堆;

每個節(jié)點的值都小于或等于其左右孩子節(jié)點的值，成為小頂堆;

完全二叉樹性質

按完全二叉樹的性質，該樹可以被順序存儲在數(shù)組中，按不同的角標進行表示。

即：

Parent(i) = (i-1)/2，i 的父節(jié)點下標

Left(i) = 2i + 1，i 的左子節(jié)點下標

Right(i) = 2(i + 1)，i 的右子節(jié)點下標

基本思想

將待排序的序列構造成一個大頂堆。此時，整個序列的最大值就是堆定的根節(jié)點，將它移走(與堆數(shù)組末尾元素交換)，再將剩余n-1個序列重新構造成一個堆，這樣就會得到第二大值，以此類推，就能得到一個有序序列了。

算法復雜度分析

在構建堆時，對每個非葉子節(jié)點來說，最多進行2次比較和互換操作，復雜度為O(n);

在進行排序時，第i次取堆頂記錄重新建堆需要用O(log i )時間，并需要取n-1次，所以重建堆的時間為O(nlogn)。

所以堆排序的時間復雜度為O(nlogn)。

實現(xiàn)步驟：

最大堆調整(Max_Heapify)：從堆的倒數(shù)第一個非葉子節(jié)點作調整，使得子節(jié)點永遠小于父節(jié)點。沒有必要從葉子節(jié)點開始，葉子節(jié)點可以看作是已符合堆特點的節(jié)點。

創(chuàng)建最大堆(Build_Max_Heap)：將堆所有數(shù)據(jù)重新排序

堆排序(HeapSort)：移除位在第一個數(shù)據(jù)的根節(jié)點，并做最大堆調整。

7. 歸并排序Merge Sort

概念：

歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的典型應用。

它指的是將兩個已經排序的序列合并成一個序列的操作。歸并排序算法依賴歸并操作。歸并排序有多路歸并排序、兩路歸并排序 , 可用于內排序，也可以用于外排序。這里僅對內排序的兩路歸并方法進行討論。

算法思路

把 n 個記錄看成 n 個長度為 l 的有序子表

進行兩兩歸并使記錄關鍵字有序，得到 n/2 個長度為 2 的有序子表

重復第 2 步直到所有記錄歸并成一個長度為 n 的有序表為止。

算法復雜度分析：

在最后一步，需要依次遍歷兩個已排序的好的數(shù)組，此時的時間復雜度為O(n)。

同時又進行著二路歸并，形成一顆完全二叉樹，此時整個排序需要進行l(wèi)og2n次。

所以歸并排序的時間復雜度為O(nlogn)。這是它的最好、最壞、平均的時間性能。

8. 快速排序Quick Sort

基本思想

通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分小，則可分別對這兩部分記錄繼續(xù)進行排序，直到整個序列有序。

復雜度分析

最好情況：partition每次劃分的都很均勻，如果排序n個關鍵字，其遞歸樹的深度就為floor(log2n)+ 1次，此時的復雜度為O(nlogn)。

如果是最壞情況，每次partition都只操作一個數(shù)字，該遞歸樹即為一顆斜樹，比較次數(shù)為n(n - 1)/2，時間復雜度為O(n2)。

平均復雜度為O(nlogn)。

9. 桶排序Bucket Sort

基本思想

工作的原理是將數(shù)組分到有限數(shù)量的桶里。每個桶再個別排序(有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序)。

步驟

設置一個定量的數(shù)組當作空桶子。

尋訪序列，并且把項目一個一個放到對應的桶子去。

對每個不是空的桶子進行排序。

從不是空的桶子里把項目再放回原來的序列中。

算法復雜度

對于N個待排數(shù)據(jù)，M個桶，平均每個桶[N/M]個數(shù)據(jù)的桶排序平均時間復雜度為：

O(N)+O(M(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-N*logM)

可以看出，最好情況即當N=M時，每個桶只有一個數(shù)據(jù)時，能夠達到O(N)。

10. 計數(shù)排序Count Sort

基本思想

計數(shù)排序是一種穩(wěn)定的線性時間排序算法。

計數(shù)排序使用一個額外的數(shù)組C，其中C數(shù)組的第i個元素是待排序數(shù)組A中值等于i的元素的個數(shù)。然后根據(jù)數(shù)組C來將A中的元素排到正確的位置。

步驟：

找出待排序的數(shù)組中最大和最小的元素

統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組 C 的第 i 項

對所有的計數(shù)累加(從C中的第一個元素開始，每一項和前一項相加)

反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1

算法復雜度分析

當輸入的元素是n個0到k之間的整數(shù)時，它的運行時間是Θ(n + k)。計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。

由于用來計數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍(等于待排序數(shù)組的最大值與最小值的差加上1)，這使得計數(shù)排序對于數(shù)據(jù)范圍很大的數(shù)組，需要大量時間和內存。