【第3篇 | 數據結構與算法】一舉消滅十大常見(常考)排序算法(原理+動圖+代碼+)

好多人 自以為 是思考，其實不過是整理了一遍自己的偏見。

作者：書偉

時間：2020/4/28

數據結構與算法 | 系列

第0篇 | 不會數據結構與算法的碼農有多牛？

第1篇 | 算法複雜度分析（必會）

第2篇 | 一文複習完7種數據結構（原理+代碼）

正文共計6000+字，19張講解算法圖片，14張代碼截圖，所有代碼均可在筆者的GitHub（https://github.com/econe-zhangwei/Data-Structures-and-Algorithms）上獲取，或者文末左下角閱讀原文可直接跳轉  。

閱讀文章之前，來思考個問題：為什麼排序是學習算法的「入門」呢？簡單？

排序有哪些好處？
排序算法分析些什麼？最好、最壞、平均情況下的時間複雜度。以及對應的要排序的原始數據是什麼樣的，因為有序度不同的數據對執行效率是有影響的。時間複雜度的係數、常數、低階。時間複雜度反應的是增長趨勢，通常忽略係數、常數、低階，但是對於小數據量，同階時間複雜度排序算法對比也要把這些考慮進來。基於比較的排序算法，涉及到元素的比較和交換，所以也要考慮比較次數和交換（或移動）次數。內存的消耗通過空間複雜度來衡量。空間複雜度是
排序算法簡單總結 & 目錄

原理： 從第一個元素開始，比較相鄰的元素的大小，若大小順序有誤，則對調後再進行下一個元素的比較。特點： 若有n個數，則需要掃描 n-1 次。每次掃描都會確定一個最大的數。

最好情況（已經有序）下，只需要進行一次冒泡操作，時間複雜度是原理：依次選擇數列中的一個元素，再從該元素後面的所有元素中找出最小值，和該元素交換位置。特點：交換操作最大為 n-1 比冒泡法少很多。比較操作最大為 n(n-1)/2, 比較次數與關鍵字的初始狀態無關。

最優情況（有序）下，搬移一次，常數個數據，只需要遍歷有序數據，找到合適的位置插入即可，所以最好時間複雜度是
插入排序先排好前面兩個數據，再把第三個元素插入到適當的位置，依次類推。插入數據之後，該數據後面的所有數據都往後挪一位。特點： 時間複雜度是

因為選擇排序，每次都是從剩餘未排序元素中找最小值和前面元素交換，所以不具有穩定性。以上三種排序算法時間複雜度都比較高，適合小規模數據。算法分析總結表格如下：
希爾排序原理： 將數據首先劃分成Y（如，8 div 2，即Y=4，稱為劃分數），得到4個區塊，插入法排好這些區塊之後，再縮小間隔，依次類推。特點： 希爾排序就是插入排序的改進版本，優化了插入排序中數據搬移的次數。相當於分組插排，先排組內得到新的數據，再縮小分組繼續插入排序。

（此圖來源於網絡，侵刪）

複雜度分析：

因為希爾排序是利用分組插排，分組的時間複雜度和遞歸的時間複雜度類似，也是

由於排序過程多次插入排序，雖然一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，所以，希爾排序是不穩定的。

歸併排序原理： 對多個已經排好序的數列通過合併的方式，將其組合成一個大的排好序的數列步驟： ① 將N個長度為1的鍵值合併成N/2個長度為2的鍵值組；②將N/2個長度為2的鍵值組合併成N//4個長度為4的鍵值組；③依次類推，知道最後合併為一組長度為N的鍵值組為止。特點：  時間複雜度是

簡單說下遞歸算法的時間複雜度分析，下篇文章再詳細介紹：如果定義求解問題a的時間是T(a)，a問題又可分解為b和c問題，求解b、c問題的時間分別是T(b)和T(c)，就有如下的遞推關係式：T(a) = T(b) + T(c) + K 。其中，K是將子問題b和c的結果合併成問題a的結果所消耗的時間。由遞歸算法的複雜度分析可知，a問題分解為子問題b和c，那麼有對應時間關係 T(a) = T(b) + T(c) +K。現假設對n個元素進行歸併排序所需時間為T(n)，分解兩個子數組排序的時間是T(n/2)，而合併兩個子數組的時間複雜度是
T(n)=2*T(n/2) + n ;   n>1，   後面的n意思就是合併兩個子數組的O(n)時間複雜度。遞推公式可以解得
快速排序（分割交換排序法）原理： 首先假設一個中間值，利用這個中間值把待排序的數據分成兩部分。小於中間值的數據放在中間值的左邊，其他數據放在中間值的右邊。對左右兩邊的數據做同樣處理，以此類推。特點： 目前公認的最快的排序法，也運用了「分而治之」的思想（歸併也是）。方法一非常簡單，這就是快排的核心思想。不過，上述方法不是最優方法，這就是為啥平時我們看到的快排都需要有「一堆」代碼來實現。我在這裡詳細分析一下這個算法的缺點在哪。
這種實現方法，在每次比較之後都需要額外的內存空間來保存小於pivot和大於pivot的數據，所以空間複雜度就變成了

那我們現在要做的就是，從未處理部分中取出一個元素 A[j] 和pivot比較，如果小於pivot，則將該元素放到已處理部分的末尾，也就是A[i]的位置。實現這個過程的做法就是交換，即 A[i]與A[j]交換。假設 A[p,…,r]=[5,3,8,2,6]，下面用圖示來說明分區的過程。

分區結束之後，就得到左邊小於pivot的部分，和右邊大於pivot的部分。對左右兩邊遞歸，就可以實現完整快速排序。快排實在是太重要了，看不懂上面那個圖示的話，再用文字寫個流程，結合來理解一下。我真是操碎了心♥啊！！！

方法二是從一個方向掃描，方法三和方法四是從兩個方向掃描，理論上都差不多。前面理解的話，後面不難理解。另外說一句，pivot的選擇直接影響到排序效率，一般是隨機初始化。方法三步驟 ① 選擇第一個元素作為基準元素pivot；②：從右向左找到小於pivot的數，若存在，R[i]和R[j]交換，i++；③ 從左往右掃描，若存在大於pivot的數，則R[i]和R[j]交換，j--；④ 重複②③，直到 i=j ，返回該位置，也就是pivot。⑤ 以pivot為界，把一個數據序列分成兩個子數據序列，然後對子序列遞歸快速排序。（左序列都比pivot小，右序列都比pivot大）方法四步驟： ① 假設鍵值 ② 從左向右找出鍵值 ③ 從右向左找出鍵值 原理：先將要排序的數據分到幾個有序的桶裡，對每個桶裡的數據分別單獨排序。然後把桶裡的數據按順序取出，最後得到的就是排好序的數據。特點：適用於數據容易劃分成m個桶，且桶於桶之間有天然的大小順序，數據範圍有小的情況。

假設有n個數據，均勻分到m個桶中，則每個桶裡有k=n/m個元素。每個桶裡用快排的話，時間複雜度是
計數排序法
原理：和桶排序相比，計數排序相當於把n個數據放在n個桶裡，依次按序讀取每個桶裡的數據即可。只需要遍歷桶裡的數據就可以得到排序結果，所以時間複雜度是特點（適用場景）：數據範圍小；非負整數（或者可以轉化為非負整數）；各個桶之間的數據分布比較均勻。

上面這個方法中我用到了python中的extend()函數，這算是一個小trick。當然這種思想也是不錯的，還有一種比較主流的實現計數排序的方式我下面也介紹一下，因為這種實現思想也很巧妙，值得學習。光用文字不容易講清楚，所以我會畫一些圖來輔助理解。假設現在有一個待排序數組 A[7]=[2,0,3,2,4,3,2]，遍歷數組A然後用5個桶（數組B）分別記錄下來每個數出現的次數。其中index 對應 原數組中的數據，value對應該數據出現的次數。

從上圖中可以看到，index=3出現的次數是value=2次，小於index=3的數出現了4次。因此，index=3的數據在排好序的數組（用C表示）中，對應的下標位置是4和5。如下圖所示，最後排好序之後，數據3一定是這麼這麼存儲的。

所以，接下來就是需要思考，該如何把數據存儲在相應的位置上。首先，先對數組B按順序求和，然後數組B就會變成如下所示。也就是說B[k]裡存的是小於等於k的數的個數。

其次，從後往前遍歷原數組A[7]=[2,0,3,2,4,3,2]。當遍歷第一個2時，就從數組B[2]中取出對應的value=4，放到C[3]（第4個元素）中，因為小於等於2的數據有4個。然後B[2]要減少1，即B[2]=3（減1的原因是為了計算後面出現的重複數據）。接下來遍歷3時，從數組B[3]中取出6放到C[5]中，然後B[3]要減1，即B[3]=5。完整過程如下圖所示，實質就是把數組B中的index變成value，value變成index的一個過程。

代碼中的 alist，counts，result分別對應上圖中的A[]，B[]，C[]。計數排序本質上就是桶排序的一種特殊情況，所以複雜度和桶排序是一樣的，這裡 就不再贅述了。
基數排序法原理： 根據不同位數上的大小來進行排序。設置0~9十個暫存數組，首先比較序列中每個數的個位數，排出順序，放到相應數組中。然後按十位數上的大小排序，依次類推。（最低位優先）特點（適用場景）：數據可以分割出獨立的「位」來進行比較；位與位直接有遞進關係（如十位比個位小）；位的數據範圍不能太大，可以用線性排序來解決，否則就不是複雜度分析：用桶排序或者計數排序對每一位（eg. 十位或百位）進行排序可以做到
堆排序法原理：堆排序的過程類似於堆的刪除操作。第一步，把堆頂元素和下標為n的堆尾元素交換位置；第二步，將前n-1個元素重新堆化；第三步，再把堆頂元素和下標為n-1位置的元素交換，依次迭代。直到最後剩下一個元素為止。特點： 堆排序兩個步驟包括建堆和排序，排序的兩個步驟是交換和堆化。

完整實現可參考下圖[6]

建堆的原理實現在上一篇文章最後已經介紹，這裡為了方便理解再把代碼寫一下方便說明，具體內容參見上篇文章（一文複習完七種數據結構）當然，你假設已經有一個建好的堆，直接用來排序就好了，排序才是這篇文章的重點。關於建堆的複雜度為什麼是

原創不易，您的「在看」

就是支持我最大的動力！

感謝您一直以來的鼓勵！

感謝您的認可，我們一起成長