程序員如何「煉」成演算法大師？

作者 | 菠了個菜

責編| 郭芮

排序演算法是《數據結構與演算法》中最基本的演算法之一。

排序演算法可以分為內部排序和外部排序：內部排序是數據記錄在內存中進行排序；而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。

常見的內部排序演算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等。

用一張圖概括：

時間複雜度與空間複雜度

關於時間複雜度：

平方階 (O(n2)) 排序，各類簡單排序：直接插入、直接選擇和冒泡排序；

線性對數階 (O(nlog2n)) 排序：快速排序、堆排序和歸併排序；

O(n1+§)) 排序，§ 是介於 0 和 1 之間的常數：希爾排序；

線性階 (O(n)) 排序：基數排序，此外還有桶、箱排序。

關於穩定性：

穩定的排序演算法：冒泡排序、插入排序、歸併排序和基數排序；

不是穩定的排序演算法：選擇排序、快速排序、希爾排序、堆排序。

冒泡排序

1.1 演算法步驟

比較相鄰的元素，如果第一個比第二個大，就交換他們兩個；

對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數；

針對所有的元素重複以上的步驟，除了最後一個；

持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

1.2 動畫演示

冒泡排序動畫演示

1.3 參考代碼

選擇排序

2.1 演算法步驟

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；

再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾；

重複第二步，直到所有元素均排序完畢。

2.2 動畫演示

選擇排序動畫演示

2.3 參考代碼

插入排序

3.1 演算法步驟

將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最後一個元素當成是未排序序列；

從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的後面）。

3.2 動畫演示

插入排序動畫演示

3.3 參考代碼

希爾排序

4.1 演算法步驟

選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列個數 k，對序列進行 k 趟排序；

每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

4.2 動畫演示

希爾排序動畫演示

4.3 參考代碼

歸併排序

5.1 演算法步驟

申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列；

設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置；

重複步驟 3 直到某一指針達到序列尾；

將另一序列剩下的所有元素直接複製到合併序列尾。

5.2 動畫演示

歸併排序動畫演示

5.3 參考代碼

快速排序

6.1 演算法步驟

從數列中挑出一個元素，稱為 「基準」（pivot）;

重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作；

遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

6.2 動畫演示

快速排序動畫演示

6.3 參考代碼

堆排序

7.1 演算法步驟

創建一個堆 H[0……n-1]；

把堆首（最大值）和堆尾互換；

把堆的尺寸縮小 1，並調用 shift_down(0)，目的是把新的數組頂端數據調整到相應位置；

重複步驟 2，直到堆的尺寸為 1。

7.2 動畫演示

堆排序動畫演示

7.3 參考代碼

計數排序

8.1 演算法步驟

花O(n)的時間掃描一下整個序列 A，獲取最小值 min 和最大值 max；

開闢一塊新的空間創建新的數組 B，長度為 ( max - min + 1)；

數組 B 中 index 的元素記錄的值是 A 中某元素出現的次數；

最後輸出目標整數序列，具體的邏輯是遍曆數組 B，輸出相應元素以及對應的個數。

8.2 動畫演示

計數排序動畫演示

8.3 參考代碼

桶排序

9.1 演算法步驟

設置固定數量的空桶；

把數據放到對應的桶中；

對每個不為空的桶中數據進行排序；

拼接不為空的桶中數據，得到結果。

9.2 動畫演示

桶排序動畫演示

9.3 參考代碼

基數排序

10.1 演算法步驟

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零；

從最低位開始，依次進行一次排序；

從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。

10.2 動畫演示

基數排序動畫演示

10.3 參考代碼

作者：菠了個菜，本文首發於個人公眾號「五分鐘學演算法」，致力於通過各種動畫的形式來描繪出各種數據結構，並圖解LeetCode原題的學習平台。

聲明：本文為作者投稿，版權歸其個人所有。

熱 文推 薦

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！