這或許是東半球分析十大排序演算法最好的一篇文章

科技 06-20

作者 | 不該相遇在秋天

轉載自五分鐘學演算法（ID:CXYxiaowu）

前言

本文全長 14237 字，配有 70 張圖片和動畫，和你一起一步步看懂排序演算法的運行過程。

預計閱讀時間 47 分鐘，強烈建議先收藏然後通過電腦端進行閱讀。

No.1 冒泡排序

冒泡排序無疑是最為出名的排序演算法之一，從序列的一端開始往另一端冒泡（你可以從左往右冒泡，也可以從右往左冒泡，看心情），依次比較相鄰的兩個數的大小（到底是比大還是比小也看你心情）。

▌圖解冒泡排序

以 [ 8，2，5，9，7 ] 這組數字來做示例，上圖來戰：

從左往右依次冒泡，將小的往右移動

首先比較第一個數和第二個數的大小，我們發現 2 比 8 要小，那麼保持原位，不做改動。位置還是 8，2，5，9，7 。

指針往右移動一格，接著比較：

比較第二個數和第三個數的大小，發現 2 比 5 要小，所以位置交換，交換後數組更新為：[ 8，5，2，9，7 ]。

指針再往右移動一格，繼續比較：

比較第三個數和第四個數的大小，發現 2 比 9 要小，所以位置交換，交換後數組更新為：[ 8，5，9，2，7 ]

同樣，指針再往右移動，繼續比較：

比較第 4 個數和第 5 個數的大小，發現 2 比 7 要小，所以位置交換，交換後數組更新為：[ 8，5，9，7，2 ]

下一步，指針再往右移動，發現已經到底了，則本輪冒泡結束，處於最右邊的 2 就是已經排好序的數字。

通過這一輪不斷的對比交換，數組中最小的數字移動到了最右邊。

接下來繼續第二輪冒泡：

由於右邊的 2 已經是排好序的數字，就不再參與比較，所以本輪冒泡結束，本輪冒泡最終冒到頂部的數字 5 也歸於有序序列中，現在數組已經變化成了[ 8，9，7，5，2 ]。

讓我們開始第三輪冒泡吧！

由於 8 比 7 大，所以位置不變，此時第三輪冒泡也已經結束，第三輪冒泡的最後結果是[ 9，8，7，5，2 ]

緊接著第四輪冒泡：

9 和 8 比，位置不變，即確定了 8 進入有序序列，那麼最後只剩下一個數字 9 ，放在末尾，自此排序結束。

▌代碼實現

冒泡的代碼還是相當簡單的，兩層循環，外層冒泡輪數，裡層依次比較，江湖中人人盡皆知。

我們看到嵌套循環，應該立馬就可以得出這個演算法的時間複雜度為O(n2)。

▌冒泡優化

冒泡有一個最大的問題就是這種演算法不管不管你有序還是沒序，閉著眼睛把你循環比較了再說。

比如我舉個數組例子：[ 9，8，7，6，5 ]，一個有序的數組，根本不需要排序，它仍然是雙層循環一個不少的把數據遍歷乾淨，這其實就是做了沒必要做的事情，屬於浪費資源。

針對這個問題，我們可以設定一個臨時遍歷來標記該數組是否已經有序，如果有序了就不用遍歷了。

No.2選擇排序

選擇排序的思路是這樣的：首先，找到數組中最小的元素，拎出來，將它和數組的第一個元素交換位置，第二步，在剩下的元素中繼續尋找最小的元素，拎出來，和數組的第二個元素交換位置，如此循環，直到整個數組排序完成。

至於選大還是選小，這個都無所謂，你也可以每次選擇最大的拎出來排，也可以每次選擇最小的拎出來的排，只要你的排序的手段是這種方式，都叫選擇排序。

▌圖解選擇排序

我們還是以[ 8，2，5，9，7 ]這組數字做例子。

第一次選擇，先找到數組中最小的數字 2 ，然後和第一個數字交換位置。（如果第一個數字就是最小值，那麼自己和自己交換位置，也可以不做處理，就是一個 if 的事情）

選擇排序1

第二次選擇，由於數組第一個位置已經是有序的，所以只需要查找剩餘位置，找到其中最小的數字5，然後和數組第二個位置的元素交換。

選擇排序2

第三次選擇，找到最小值 7 ，和第三個位置的元素交換位置。

選擇排序3

第四次選擇，找到最小值8，和第四個位置的元素交換位置。

最後一個到達了數組末尾，沒有可對比的元素，結束選擇。

如此整個數組就排序完成了。

▌代碼實現

雙層循環，時間複雜度和冒泡一模一樣，都是O(n2)。

No.3插入排序

插入排序的思想和我們打撲克摸牌的時候一樣，從牌堆里一張一張摸起來的牌都是亂序的，我們會把摸起來的牌插入到左手中合適的位置，讓左手中的牌時刻保持一個有序的狀態。

那如果我們不是從牌堆里摸牌，而是左手裡面初始化就是一堆亂牌呢？一樣的道理，我們把牌往手的右邊挪一挪，把手的左邊空出一點位置來，然後在亂牌中抽一張出來，插入到左邊，再抽一張出來，插入到左邊，再抽一張，插入到左邊，每次插入都插入到左邊合適的位置，時刻保持左邊的牌是有序的，直到右邊的牌抽完，則排序完畢。

▌圖解插入排序

數組初始化：[ 8，2，5，9，7 ]，我們把數組中的數據分成兩個區域，已排序區域和未排序區域，初始化的時候所有的數據都處在未排序區域中，已排序區域是空。

第一輪，從未排序區域中隨機拿出一個數字，既然是隨機，那麼我們就獲取第一個，然後插入到已排序區域中，已排序區域是空，那麼就不做比較，默認自身已經是有序的了。（當然了，第一輪在代碼中是可以省略的，從下標為1的元素開始即可）

插入排序2

第二輪，繼續從未排序區域中拿出一個數，插入到已排序區域中，這個時候要遍歷已排序區域中的數字挨個做比較，比大比小取決於你是想升序排還是想倒序排，這裡排升序：

插入排序3

第三輪，排 5 ：

插入排序4

第四輪，排 9 ：

插入排序5

第五輪，排 7

插入排序6

排序結束。

▌代碼實現

從代碼里我們可以看出，如果找到了合適的位置，就不會再進行比較了，就好比牌堆里抽出的一張牌本身就比我手裡的牌都小，那麼我只需要直接放在末尾就行了，不用一個一個去移動數據騰出位置插入到中間。

所以說，最好情況的時間複雜度是 O(n)，最壞情況的時間複雜度是 O(n2)，然而時間複雜度這個指標看的是最壞的情況，而不是最好的情況，所以插入排序的時間複雜度是 O(n2)。

No.4希爾排序

希爾排序這個名字，來源於它的發明者希爾，也稱作「縮小增量排序」，是插入排序的一種更高效的改進版本。

我們知道，插入排序對於大規模的亂序數組的時候效率是比較慢的，因為它每次只能將數據移動一位，希爾排序為了加快插入的速度，讓數據移動的時候可以實現跳躍移動，節省了一部分的時間開支。

▌圖解希爾排序

待排序數組 10 個數據：

希爾排序1

假設計算出的排序區間為 4 ，那麼我們第一次比較應該是用第 5 個數據與第 1 個數據相比較。

調換後的數據為[ 7，2，5，9，8，10，1，15，12，3 ]，然後指針右移，第 6 個數據與第 2 個數據相比較。

指針右移，繼續比較。

如果交換數據後，發現減去區間得到的位置還存在數據，那麼繼續比較，比如下面這張圖，12 和 8 相比較，原地不動後，指針從 12 跳到 8 身上，繼續減去區間發現前面還有一個下標為 0 的數據 7 ，那麼 8 和 7 相比較。

比較完之後的效果是 7，8，12 三個數為有序排列。

當最後一個元素比較完之後，我們會發現大部分值比較大的數據都似乎調整到數組的中後部分了。

假設整個數組比較長的話，比如有 100 個數據，那麼我們的區間肯定是四五十，調整後區間再縮小成一二十還會重新調整一輪，直到最後區間縮小為 1，就是真正的排序來了。

指針右移，繼續比較：

重複步驟，即可完成排序，重複的圖就不多畫了。

我們可以發現，當區間為 1 的時候，它使用的排序方式就是插入排序。

▌代碼實現

可能你會問為什麼區間要以 gap = gap*3 1 去計算，其實最優的區間計算方法是沒有答案的，這是一個長期未解決的問題，不過差不多都會取在二分之一到三分之一附近。

No.5歸併排序

歸併字面上的意思是合併，歸併演算法的核心思想是分治法，就是將一個數組一刀切兩半，遞歸切，直到切成單個元素，然後重新組裝合併，單個元素合併成小數組，兩個小數組合併成大數組，直到最終合併完成，排序完畢。

▌圖解歸併排序

我們以[ 8，2，5，9，7 ]這組數字來舉例

首先，一刀切兩半：

再切：

再切

粒度切到最小的時候，就開始歸併

數據量設定的比較少，是為了方便圖解，數據量為單數，是為了讓你看到細節，下面我畫了一張更直觀的圖可能你會更喜歡：

▌代碼實現

我們上面講過，歸併排序的核心思想是分治，分而治之，將一個大問題分解成無數的小問題進行處理，處理之後再合併，這裡我們採用遞歸來實現：

我們可以發現 merge 方法中只有一個 for 循環，直接就可以得出每次合併的時間複雜度為 O(n) ，而分解數組每次對半切割，屬於對數時間 O(log n) ，合起來等於 O(log2n) ，也就是說，總的時間複雜度為 O(nlogn) 。

關於空間複雜度，其實大部分人寫的歸併都是在 merge 方法裡面申請臨時數組，用臨時數組來輔助排序工作，空間複雜度為 O(n)，而我這裡做的是原地歸併，只在最開始申請了一個臨時數組，所以空間複雜度為 O(1)。

如果你對空間複雜度這一塊不太了解，可以查看小吳之前的數據結構系列文章---冰與火之歌：「時間」與「空間」複雜度。

No.6快速排序

快速排序的核心思想也是分治法，分而治之。它的實現方式是每次從序列中選出一個基準值，其他數依次和基準值做比較，比基準值大的放右邊，比基準值小的放左邊，然後再對左邊和右邊的兩組數分別選出一個基準值，進行同樣的比較移動，重複步驟，直到最後都變成單個元素，整個數組就成了有序的序列。

（周知：動圖裡面的大於小於寫反，小吳修正重新錄製後，上傳新動圖到微信後台卻一直失敗）

▌圖解快速排序

我們以[ 8，2，5，0，7，4，6，1 ]這組數字來進行演示

首先，我們隨機選擇一個基準值：

快速排序1

與其他元素依次比較，大的放右邊，小的放左邊：

然後我們以同樣的方式排左邊的數據：

繼續排 0 和 1 ：

由於只剩下一個數，所以就不用排了，現在的數組序列是下圖這個樣子：

右邊以同樣的操作進行，即可排序完成。

▌單邊掃描

快速排序的關鍵之處在於切分，切分的同時要進行比較和移動，這裡介紹一種叫做單邊掃描的做法。

我們隨意抽取一個數作為基準值，同時設定一個標記 mark 代表左邊序列最右側的下標位置，當然初始為 0 ，接下來遍曆數組，如果元素大於基準值，無操作，繼續遍歷，如果元素小於基準值，則把 mark 1 ，再將 mark 所在位置的元素和遍歷到的元素交換位置，mark 這個位置存儲的是比基準值小的數據，當遍歷結束後，將基準值與 mark 所在元素交換位置即可。

▌代碼實現

▌雙邊掃描

另外還有一種雙邊掃描的做法，看起來比較直觀：我們隨意抽取一個數作為基準值，然後從數組左右兩邊進行掃描，先從左往右找到一個大於基準值的元素，將下標指針記錄下來，然後轉到從右往左掃描，找到一個小於基準值的元素，交換這兩個元素的位置，重複步驟，直到左右兩個指針相遇，再將基準值與左側最右邊的元素交換。

我們來看一下實現代碼，不同之處只有 partition 方法：

▌極端情況

快速排序的時間複雜度和歸併排序一樣，O(n log n)，但這是建立在每次切分都能把數組一刀切兩半差不多大的前提下，如果出現極端情況，比如排一個有序的序列，如[ 9，8，7，6，5，4，3，2，1 ]，選取基準值 9 ，那麼需要切分 n - 1 次才能完成整個快速排序的過程，這種情況下，時間複雜度就退化成了 O(n2)，當然極端情況出現的概率也是比較低的。

所以說，快速排序的時間複雜度是 O(nlogn)，極端情況下會退化成 O(n2)，為了避免極端情況的發生，選取基準值應該做到隨機選取，或者是打亂一下數組再選取。

另外，快速排序的空間複雜度為 O(1)。

No.7堆排序

堆排序顧名思義，是利用堆這種數據結構來進行排序的演算法。

如果你了解堆這種數據結構，你應該知道堆是一種優先隊列，兩種實現，最大堆和最小堆，由於我們這裡排序按升序排，所以就直接以最大堆來說吧。

我們完全可以把堆（以下全都默認為最大堆）看成一棵完全二叉樹，但是位於堆頂的元素總是整棵樹的最大值，每個子節點的值都比父節點小，由於堆要時刻保持這樣的規則特性，所以一旦堆裡面的數據發生變化，我們必須對堆重新進行一次構建。

既然堆頂元素永遠都是整棵樹中的最大值，那麼我們將數據構建成堆後，只需要從堆頂取元素不就好了嗎？第一次取的元素，是否取的就是最大值？取完後把堆重新構建一下，然後再取堆頂的元素，是否取的就是第二大的值？反覆的取，取出來的數據也就是有序的數據。

▌圖解堆排序

我們以[ 8，2，5，9，7，3 ]這組數據來演示。

首先，將數組構建成堆。

既然構建成堆結構了，那麼接下來，我們取出堆頂的數據，也就是數組第一個數 9 ，取法是將數組的第一位和最後一位調換，然後將數組的待排序範圍 -1。

現在的待排序數據是[ 3，8，5，2，7 ]，我們繼續將待排序數據構建成堆。

取出堆頂數據，這次就是第一位和倒數第二位交換了，因為待排序的邊界已經減 1 。

繼續構建堆

從堆頂取出來的數據最終形成一個有序列表，重複的步驟就不再贅述了，我們來看一下代碼實現。

▌代碼實現

堆排序和快速排序的時間複雜度都一樣是 O(nlogn)。

No.8計數排序

計數排序是一種非基於比較的排序演算法，我們之前介紹的各種排序演算法幾乎都是基於元素之間的比較來進行排序的，計數排序的時間複雜度為 O(n m )，m 指的是數據量，說的簡單點，計數排序演算法的時間複雜度約等於 O(n)，快於任何比較型的排序演算法。

▌圖解計數排序

以下以[ 3，5，8，2，5，4 ]這組數字來演示。

首先，我們找到這組數字中最大的數，也就是 8，創建一個最大下標為 8 的空數組 arr 。

遍曆數據，將數據的出現次數填入arr中對應的下標位置中。

遍歷 arr ，將數據依次取出即可。

▌代碼實現

▌穩定排序

有一個需求就是當對成績進行排名次的時候，如何在原來排前面的人，排序後還是處於相同成績的人的前面。

解題的思路是對 countArr 計數數組進行一個變形，變來和名次掛鉤，我們知道 countArr 存放的是分數的出現次數，那麼其實我們可以算出每個分數的最大名次，就是將 countArr 中的每個元素順序求和。

如下圖：

變形之後是什麼意思呢？

我們把原數組[ 2，5，8，2，5，4 ]中的數據依次拿來去 countArr 去找，你會發現 3 這個數在 countArr[3] 中的值是 2 ，代表著排名第二名，（因為第一名是最小的 2，對吧？），5 這個數在 countArr[5] 中的值是 5 ，為什麼是 5 呢？我們來數數，排序後的數組應該是[ 2，3，4，5，5，8 ]，5 的排名是第五名，那 4 的排名是第幾名呢？對應 countArr[4] 的值是 3 ，第三名，5 的排名是第五名是因為 5 這個數有兩個，自然佔據了第 4 名和第 5 名。

所以我們取排名的時候應該特別注意，原數組中的數據要從右往左取，從 countArr 取出排名後要把 countArr 中的排名減 1 ，以便於再次取重複數據的時候排名往前一位。

對應代碼實現：

計數局限性

計數排序的毛病很多，我們來找找 bug 。

如果我要排的數據里有 0 呢？ int[] 初始化內容全是 0 ，排毛線。

如果我要排的數據範圍比較大呢？比如[ 1，9999 ]，我排兩個數你要創建一個 int[10000] 的數組來計數？

對於第一個 bug ，我們可以使用偏移量來解決，比如我要排[ -1，0，-3 ]這組數字，這個簡單，我全給你們加 10 來計數，變成[ 9，10，7 ]計完數後寫回原數組時再減 10。不過有可能也會踩到坑，萬一你數組裡恰好有一個 -10，你加上 10 後又變 0 了，排毛線。

對於第二個 bug ，確實解決不了，如果是[ 9998，9999 ]這種雖然值大但是相差範圍不大的數據我們也可以使用偏移量解決，比如這兩個數據，我減掉 9997 後只需要申請一個 int[3] 的數組就可以進行計數。

由此可見，計數排序只適用於正整數並且取值範圍相差不大的數組排序使用，它的排序的速度是非常可觀的。

No.9桶排序

桶排序可以看成是計數排序的升級版，它將要排的數據分到多個有序的桶里，每個桶里的數據再單獨排序，再把每個桶的數據依次取出，即可完成排序。

▌圖解桶排序

我們拿一組計數排序啃不掉的數據 [ 500，6123，1700，10，9999 ] 來舉例。

第一步，我們創建 10 個桶，分別來裝 0-1000 、1000-2000 、 2000-3000 、 3000-4000 、 4000-5000 、5000-6000、 6000-7000 、7000-8000 、8000-9000 區間的數據。

第二步，遍歷原數組，對號入桶。

第三步，對桶中的數據進行單獨排序，只有第一個桶中的數量大於 1 ，顯然只需要排第一個桶。

最後，依次將桶中的數據取出，排序完成。

▌代碼實現

這個桶排序乍一看好像挺簡單的，但是要敲代碼就需要考慮幾個問題了。

桶這個東西怎麼表示？

怎麼確定桶的數量？

桶內排序用什麼方法排？

代碼如下：

桶當然是一個可以存放數據的集合，我這裡使用 arrayList ，如果你使用 LinkedList 那其實也是沒有問題的。

桶的數量我認為設置為原數組的長度是合理的，因為理想情況下每個數據裝一個桶。

數據入桶的映射演算法其實是一個開放性問題，我承認我這裡寫的方案並不佳，因為我測試過不同的數據集合來排序，如果你有什麼更好的方案或想法，歡迎留言討論。

桶內排序為了方便起見使用了當前語言提供的排序方法，如果對於穩定排序有所要求，可以選擇使用自定義的排序演算法。

▌桶排序的思考及其應用

在額外空間充足的情況下，盡量增大桶的數量，極限情況下每個桶只有一個數據時，或者是每隻桶只裝一個值時，完全避開了桶內排序的操作，桶排序的最好時間複雜度就能夠達到 O(n)。

比如高考總分 750 分，全國幾百萬人，我們只需要創建 751 個桶，循環一遍挨個扔進去，排序速度是毫秒級。

但是如果數據經過桶的劃分之後，桶與桶的數據分布極不均勻，有些數據非常多，有些數據非常少，比如[ 8，2，9，10，1，23，53，22，12，9000 ]這十個數據，我們分成十個桶裝，結果發現第一個桶裝了 9 個數據，這是非常影響效率的情況，會使時間複雜度下降到 O(nlogn)，解決辦法是我們每次桶內排序時判斷一下數據量，如果桶里的數據量過大，那麼應該在桶裡面回調自身再進行一次桶排序。

No.10基數排序

基數排序是一種非比較型整數排序演算法，其原理是將數據按位數切割成不同的數字，然後按每個位數分別比較。

假設說，我們要對 100 萬個手機號碼進行排序，應該選擇什麼排序演算法呢？排的快的有歸併、快排時間複雜度是 O(nlogn)，計數排序和桶排序雖然更快一些，但是手機號碼位數是11位，那得需要多少桶？內存條表示不服。

這個時候，我們使用基數排序是最好的選擇。