在前兩節課里，我們學習了面試中常用的以及幾個較為復雜的數據結構，它們是學好算法的基石。
算法學習其實是一種提高思維能力的過程。無論是學習算法，還是在面試或實際的工作、生活中，我們都會碰見一些從沒遇到過的問題。解決方法也類似，先推敲最直觀的解法，再對某個步驟進行優化。例如，講前綴樹的例題時，我們正是為了要提高匹配字符串的速度才借用了前綴樹的。
從這節課開始，我們會將寶貴的時間、精力針對性地去學習面試中最常考的、最核心的算法。而這節課要學習的是排序算法，包括：
1. 基本的排序算法
冒泡排序（Bubble Sort）
插入排序（Insertion Sort）
2. 常考的排序算法
歸并排序（Merge Sort）
快速排序（Quick Sort）
拓撲排序（Topological Sort）
3. 其他排序算法
堆排序（Heap Sort）
桶排序（Bucket Sort)
注意：
1. 冒泡排序和插入排序是最基礎的，面試官有時候喜歡拿它們來考察你的基礎知識，并且看看你能不能快速地寫出沒有 bug 的代碼。
2. 歸并排序、快速排序和拓撲排序的思想是解決絕大部分涉及排序問題的關鍵，我們將在這節課里重點介紹它們。
3. 堆排序和桶排序，本節課不作深入研究，但有時間的話一定要看看，尤其是桶排序，在一定的場合中（例如知道所有元素出現的范圍時），能在線性的時間復雜度里解決戰斗，掌握好它的解題思想能開闊解題思路。
* [ ] 冒泡排序（Bubble Sort）
* 基本思想
給定一個數組，我們把數組里的元素通通倒入到水池中，這些元素將通過相互之間的比較，按照大小順序一個一個地像氣泡一樣浮出水面。
* 實現
每一輪，從雜亂無章的數組頭部開始，每兩個元素比較大小并進行交換，直到這一輪當中最大或最小的元素被放置在數組的尾部，然后不斷地重復這個過程，直到所有元素都排好位置。其中，核心操作就是元素相互比較。
* 例題分析
給定數組 [2, 1, 7, 9, 5, 8]，要求按照從左到右、從小到大的順序進行排序。?
* 解題思路
從左到右依次冒泡，把較大的數往右邊挪動即可。
?
1. 首先指針指向第一個數，比較第一個數和第二個數的大小，由于 2 比 1 大，所以兩兩交換，[1, 2, 7, 9, 5, 8]。
2. 接下來指針往前移動一步，比較 2 和 7，由于 2 比 7 小，兩者保持不動，[1, 2, 7, 9, 5, 8]。到目前為止，7 是最大的那個數。
3. 指針繼續往前移動，比較 7 和 9，由于 7 比 9 小，兩者保持不動，[1, 2, 7, 9, 5, 8]。現在，9 變成了最大的那個數。
4. 再往后，比較 9 和 5，很明顯，9 比 5 大，交換它們的位置，[1, 2, 7, 5, 9, 8]。
5. 最后，比較 9 和 8，9 比 8 大，交換它們的位置，[1, 2, 7, 5, 8, 9]。經過第一輪的兩兩比較，9 這個最大的數就像冒泡一樣冒到了數組的最后面。
接下來進行第二輪的比較，把指針重新指向第一個元素，重復上面的操作，最后，數組變成了：[1, 2, 5, 7, 8, 9]。
在進行新一輪的比較中，判斷一下在上一輪比較的過程中有沒有發生兩兩交換，如果一次交換都沒有發生，就證明其實數組已經排好序了。
**代碼示例**
```
void?sort(int[]?nums)?{
????//定義一個布爾變量?hasChange，用來標記每輪遍歷中是否發生了交換
????boolean?hasChange?=?true;?
????//每輪遍歷開始，將?hasChange?設置為?false
????for?(int?i?=?0;?i?<?nums.length?-?1?&&?hasChange;?i++)?{
????????hasChange?=?false;
????????//進行兩兩比較，如果發現當前的數比下一個數還大，那么就交換這兩個數，同時記錄一下有交換發生
????????for?(int?j?=?0;?j?<?nums.length?-?1?-?i;?j++)?{
????????????if?(nums[j]?>?nums[j?+?1])?{
????????????????swap(nums,?j,?j?+?1);
????????????????hasChange?=?true;
????????????}
????????}
?????}
?}
```
**算法分析**
* 空間復雜度
假設數組的元素個數是 n，由于在整個排序的過程中，我們是直接在給定的數組里面進行元素的兩兩交換，所以空間復雜度是 O(1)。
**時間復雜度**
1. 給定的數組按照順序已經排好
在這種情況下，我們只需要進行 n?1 次的比較，兩兩交換次數為 0，時間復雜度是 O(n)。這是最好的情況。
2. 給定的數組按照逆序排列
在這種情況下，我們需要進行 n(n-1)/2 次比較，時間復雜度是 O(n2)。這是最壞的情況。
3. 給定的數組雜亂無章
在這種情況下，平均時間復雜度是 O(n2)。
由此可見，冒泡排序的時間復雜度是 O(n2)。它是一種穩定的排序算法。（穩定是指如果數組里兩個相等的數，那么排序前后這兩個相等的數的相對位置保持不變。）
* [ ] 插入排序（Insertion Sort）
* 基本思想
不斷地將尚未排好序的數插入到已經排好序的部分。
* 特點
在冒泡排序中，經過每一輪的排序處理后，數組后端的數是排好序的；而對于插入排序來說，經過每一輪的排序處理后，數組前端的數都是排好序的。
* 例題分析
對數組 [2, 1, 7, 9, 5, 8] 進行插入排序。
* 解題思路
首先將數組分成左右兩個部分，左邊是已經排好序的部分，右邊是還沒有排好序的部分，剛開始，左邊已排好序的部分只有第一個元素 2。接下來，我們對右邊的元素一個一個進行處理，將它們放到左邊。
1. 先來看 1，由于 1 比 2 小，需要將 1 插入到 2 的前面，做法很簡單，兩兩交換位置即可，[1, 2, 7, 9, 5, 8]。
2. 然后，我們要把 7 插入到左邊的部分，由于 7 已經比 2 大了，表明它是目前最大的元素，保持位置不變，[1, 2, 7, 9, 5, 8]。
3. 同理，9 也不需要做位置變動，[1, 2, 7, 9, 5, 8]。
4. 接下來，如何把 5 插入到合適的位置。首先比較 5 和 9，由于 5 比 9 小，兩兩交換，[1, 2, 7, 5, 9, 8]，繼續，由于 5 比 7 小，兩兩交換，[1, 2, 5, 7, 9, 8]，最后，由于 5 比 2 大，此輪結束。
5. 最后一個數是 8，由于 8 比 9 小，兩兩交換，[1, 2, 5, 7, 8, 9]，再比較 7 和 8，發現 8 比 7 大，此輪結束。到此，插入排序完畢。
* 代碼示例
```
void?sort(int[]?nums)?{
????//?將數組的第一個元素當作已經排好序的，從第二個元素，即?i?從?1?開始遍歷數組
????for?(int?i?=?1,?j,?current;?i?<?nums.length;?i++)?{
????????//?外圍循環開始，把當前?i?指向的值用?current?保存
????????current?=?nums[i];
????????//?指針?j?內循環，和?current?值比較，若?j?所指向的值比?current?值大，則該數右移一位
????????for?(j?=?i?-?1;?j?>=?0?&&?nums[j]?>?current;?j--)?{
????????????nums[j?+?1]?=?nums[j];
????????????}
????
????????//?內循環結束，j+1?所指向的位置就是?current?值插入的位置
????????nums[j?+?1]?=?current;
????}
}
```
**算法分析**
* 空間復雜度
假設數組的元素個數是 n，由于在整個排序的過程中，是直接在給定的數組里面進行元素的兩兩交換，空間復雜度是 O(1)。
**時間復雜度**
1. 給定的數組按照順序已經排好
只需要進行 n-1 次的比較，兩兩交換次數為 0，時間復雜度是 O(n)。這是最好的情況。
2. 給定的數組按照逆序排列
在這種情況下，我們需要進行 n(n-1)/2 次比較，時間復雜度是?O(n2)。這是最壞的情況。
3. 給定的數組雜亂無章
在這種情況下，平均時間復雜度是?O(n2)。
由此可見，和冒泡排序一樣，插入排序的時間復雜度是?O(n2)，并且它也是一種穩定的排序算法。
建議：LeetCode 第 147 題，要求對一個鏈表進行插入排序，希望大家去試一試。
* [ ] 歸并排序（Merge Sort）
* 基本思想
核心是分治，就是把一個復雜的問題分成兩個或多個相同或相似的子問題，然后把子問題分成更小的子問題，直到子問題可以簡單的直接求解，最原問題的解就是子問題解的合并。歸并排序將分治的思想體現得淋漓盡致。
* 實現
一開始先把數組從中間劃分成兩個子數組，一直遞歸地把子數組劃分成更小的子數組，直到子數組里面只有一個元素，才開始排序。
排序的方法就是按照大小順序合并兩個元素，接著依次按照遞歸的返回順序，不斷地合并排好序的子數組，直到最后把整個數組的順序排好。
**代碼示例**
主體函數的代碼實現如下。
```
void?sort(int[]?A,?int?lo,?int?hi)?{
??//?判斷是否只剩下最后一個元素
??if?(lo?>=?hi)?return;
??
??//?從中間將數組分成兩個部分
??int?mid?=?lo?+?(hi?-?lo)?/?2;
??
??//?分別遞歸地將左右兩半排好序
??sort(A,?lo,?mid);
??sort(A,?mid?+?1,?hi);
??//?將排好序的左右兩半合并??
??merge(A,?lo,?mid,?hi);
}
```
歸并操作的代碼實現如下。
```
void?merge(int[]?nums,?int?lo,?int?mid,?int?hi)?{
????//?復制一份原來的數組
????int[]?copy?=?nums.clone();
??
????//?定義一個?k?指針表示從什么位置開始修改原來的數組，i?指針表示左半邊的起始位置，j?表示右半邊的起始位置
????int?k?=?lo,?i?=?lo,?j?=?mid?+?1;
??
????while?(k?<=?hi)?{
????????if?(i?>?mid)?{
????????????nums[k++]?=?copy[j++];
????????}?else?if?(j?>?hi)?{
??????????nums[k++]?=?copy[i++];
????????}?else?if?(copy[j]?<?copy[i])?{
??????????nums[k++]?=?copy[j++];
????????}?else?{
??????????nums[k++]?=?copy[i++];
????????}
????}
}
```
其中，While 語句比較，一共可能會出現四種情況。
* 左半邊的數都處理完畢，只剩下右半邊的數，只需要將右半邊的數逐個拷貝過去。
* 右半邊的數都處理完畢，只剩下左半邊的數，只需要將左半邊的數逐個拷貝過去就好。
* 右邊的數小于左邊的數，將右邊的數拷貝到合適的位置，j 指針往前移動一位。
* 左邊的數小于右邊的數，將左邊的數拷貝到合適的位置，i 指針往前移動一位。
* 例題分析
例題：利用歸并排序算法對數組 [2, 1, 7, 9, 5, 8] 進行排序。
* 解題思路
首先不斷地對數組進行切分，直到各個子數組里只包含一個元素。
接下來遞歸地按照大小順序合并切分開的子數組，遞歸的順序和二叉樹里的前向遍歷類似。
1. 合并 [2] 和 [1] 為 [1, 2]。
2. 子數組 [1, 2] 和 [7] 合并。
3. 右邊，合并 [9] 和 [5]。
4. 然后合并 [5, 9] 和 [8]。
5. 最后合并 [1, 2, 7] 和 [5, 8, 9] 成 [1, 2, 5, 8, 9]，就可以把整個數組排好序了。
合并數組 [1, 2, 7] 和 [5, 8, 9] 的操作步驟如下。
1. 把數組 [1, 2, 7] 用 L 表示，[5, 8, 9] 用 R 表示。
2. 合并的時候，開辟分配一個新數組 T 保存結果，數組大小應該是兩個子數組長度的總和
3. 然后下標 i、j、k 分別指向每個數組的起始點。
4. 接下來，比較下標i和j所指向的元素 L[i] 和 R[j]，按照大小順序放入到下標 k 指向的地方，1 小于 5。
5. 移動 i 和 k，繼續比較 L[i] 和 R[j]，2 比 5 小。
6. i 和 k 繼續往前移動，5 比 7 小。
7. 移動 j 和 k，繼續比較 L[i] 和 R[j]，7 比 8 小。
8. 這時候，左邊的數組已經處理完畢，直接將右邊數組剩余的元素放到結果數組里就好。
合并之所以能成功，先決條件必須是兩個子數組都已經分別排好序了。
**算法分析**
* 空間復雜度
由于合并 n 個元素需要分配一個大小為 n 的額外數組，合并完成之后，這個數組的空間就會被釋放，所以算法的空間復雜度就是 O(n)。歸并排序也是穩定的排序算法。
* 時間復雜度
歸并算法是一個不斷遞歸的過程。
舉例：數組的元素個數是 n，時間復雜度是 T(n) 的函數。
解法：把這個規模為 n 的問題分成兩個規模分別為 n/2 的子問題，每個子問題的時間復雜度就是 T(n/2)，那么兩個子問題的復雜度就是 2×T(n/2)。當兩個子問題都得到了解決，即兩個子數組都排好了序，需要將它們合并，一共有 n 個元素，每次都要進行最多 n-1 次的比較，所以合并的復雜度是 O(n)。由此我們得到了遞歸復雜度公式：T(n) = 2×T(n/2) + O(n)。
對于公式求解，不斷地把一個規模為 n 的問題分解成規模為 n/2 的問題，一直分解到規模大小為 1。如果 n 等于 2，只需要分一次；如果 n 等于 4，需要分 2 次。這里的次數是按照規模大小的變化分類的。
以此類推，對于規模為 n 的問題，一共要進行 log(n) 層的大小切分。在每一層里，我們都要進行合并，所涉及到的元素其實就是數組里的所有元素，因此，每一層的合并復雜度都是 O(n)，所以整體的復雜度就是?O(nlogn)。
建議：歸并算法的思想很重要，其中對兩個有序數組合并的操作，在很多面試題里都有用到，建議大家一定要把這個算法練熟。
* [ ] 快速排序（Quick Sort）
* 基本思想
快速排序也采用了分治的思想。
* 實現
把原始的數組篩選成較小和較大的兩個子數組，然后遞歸地排序兩個子數組。
舉例：把班里的所有同學按照高矮順序排成一排。
解法：老師先隨機地挑選了同學 A，讓所有其他同學和 A 比高矮，比 A 矮的都站在 A 的左邊，比 A 高的都站在 A 的右邊。接下來，老師分別從左邊和右邊的同學里選擇了同學 B 和 C，然后不斷地篩選和排列下去。
在分成較小和較大的兩個子數組過程中，如何選定一個基準值（也就是同學 A、B、C 等）尤為關鍵。
* 例題分析
對數組 [2, 1, 7, 9, 5, 8] 進行排序。
* 解題思路
按照快速排序的思想，首先把數組篩選成較小和較大的兩個子數組。
隨機從數組里選取一個數作為基準值，比如 7，于是原始的數組就被分成了兩個子數組。注意：快速排序是直接在原始數組里進行各種交換操作，所以當子數組被分割出來的時候，原始數組里的排列也被改變了。
接下來，在較小的子數組里選 2 作為基準值，在較大的子數組里選 8 作為基準值，繼續分割子數組。
繼續將元素個數大于 1 的子數組進行劃分，當所有子數組里的元素個數都為 1 的時候，原始數組也被排好序了。
**代碼示例**
主體函數代碼如下。
```
void?sort(int[]?nums,?int?lo,?int?hi)?{
????if?(lo?>=?hi)?return;?//?判斷是否只剩下一個元素，是，則直接返回
????
????//?利用?partition?函數找到一個隨機的基準點
????int?p?=?partition(nums,?lo,?hi);
????
????//?遞歸地對基準點左半邊和右半邊的數進行排序
????sort(nums,?lo,?p?-?1);
????sort(nums,?p?+?1,?hi);
}
```
下面用代碼實現 partition 函數獲得基準值。
```
int?partition(int[]?nums,?int?lo,?int?hi)?{
????//?隨機選擇一個數作為基準值，nums[hi]?就是基準值
????swap(nums,?randRange(lo,?hi),?hi);
????int?i,?j;
????//?從左到右用每個數和基準值比較，若比基準值小，則放到指針?i?所指向的位置。循環完畢后，i?指針之前的數都比基準值小
????for?(i?=?lo,?j?=?lo;?j?<?hi;?j++)?{
????????if?(nums[j]?<=?nums[hi])?{
????????????swap(nums,?i++,?j);
????????}
????}
????//?末尾的基準值放置到指針?i?的位置，i?指針之后的數都比基準值大
????swap(nums,?i,?j);
????//?返回指針?i，作為基準點的位置
????return?i;
}
```
**算法分析**
時間復雜度
1. 最優情況：被選出來的基準值都是當前子數組的中間數。
這樣的分割，能保證對于一個規模大小為 n 的問題，能被均勻分解成兩個規模大小為 n/2 的子問題（歸并排序也采用了相同的劃分方法），時間復雜度就是：T(n) = 2×T(n/2) + O(n)。
把規模大小為 n 的問題分解成 n/2 的兩個子問題時，和基準值進行了 n-1 次比較，復雜度就是 O(n)。很顯然，在最優情況下，快速排序的復雜度也是?O(nlogn)。
2. 最壞情況：基準值選擇了子數組里的最大或者最小值
每次都把子數組分成了兩個更小的子數組，其中一個的長度為 1，另外一個的長度只比原子數組少 1。
舉例：對于數組來說，每次挑選的基準值分別是 9、8、7、5、2。
解法：劃分過程和冒泡排序的過程類似。
算法復雜度為?O(n2)。
提示：可以通過隨機地選取基準值來避免出現最壞的情況。
空間復雜度
和歸并排序不同，快速排序在每次遞歸的過程中，只需要開辟 O(1) 的存儲空間來完成交換操作實現直接對數組的修改，又因為遞歸次數為 logn，所以它的整體空間復雜度完全取決于壓堆棧的次數，因此它的空間復雜度是 O(logn)。
舉例：LeetCode 第 215 題，給定一個尚未排好序的數組，要求找出第 k 大的數。
解法 1：直接將數組進行排序，然后得出結果。
解法 2：快速排序。
每次隨機選取一個基準值，將數組分成較小的一半和較大的一半，然后檢查這個基準值最后所在的下標是不是 k，算法復雜度只需要 O(n)。
* [ ] 拓撲排序（Topological Sort）
* 基本思想
和前面介紹的幾種排序不同，拓撲排序應用的場合不再是一個簡單的數組，而是研究圖論里面頂點和頂點連線之間的性質。拓撲排序就是要將這些頂點按照相連的性質進行排序。
要能實現拓撲排序，得有幾個前提：
* 圖必須是有向圖
* 圖里面沒有環
拓撲排序一般用來理清具有依賴關系的任務。
舉例：假設有三門課程 A、B、C，如果想要學習課程 C 就必須先把課程 B 學完，要學習課程 B，還得先學習課程 A，所以得出課程的學習順序應該是 A -> B -> C。
**實現**
將問題用一個有向無環圖（DAG, Directed Acyclic Graph）進行抽象表達，定義出哪些是圖的頂點，頂點之間如何互相關聯。
可以利用廣度優先搜索或深度優先搜索來進行拓撲排序。
**例題分析**
有一個學生想要修完 5 門課程的學分，這 5 門課程分別用 1、2、3、4、5 來表示，現在已知學習這些課程有如下的要求：
* 課程 2 和 4 依賴于課程 ?1
* 課程 3 依賴于課程 2 和 4
* 課程 4 依賴于課程 1 和 2
* 課程 5 依賴于課程 3 和 4
那么這個學生應該按照怎樣的順序來學習這 5 門課程呢？
**解題思路**
可以把 5 門課程看成是一個圖里的 5 個頂點，用有向線段按照它們的相互關系連起來，于是得出下面的有向圖。
首先可以看到，這個有向圖里沒有環，無論從哪個頂點出發，都不會再回到那個頂點。并且，這個圖里并沒有孤島的出現，因此，我們可以對它進行拓撲排序。
方法就是，一開始的時候，對每個頂點統計它們各自的前驅（也就是入度）：1(0)，2(1)，3(2)，4(1)，5(2)。
1. 選擇其中一個沒有前驅（也就是入度為 0）的頂點，在這道題里面，頂點 1 就是我們要找的那個點，將它作為結果輸出。同時刪除掉該頂點和所有以它作為起始點的有向邊，更新頂點的入度表。
2. 接下來，頂點 2 就是下一個沒有前驅的頂點，輸出頂點 2，并將以它作為起點的有向邊刪除，同時更新入度表。
3. 再來，頂點 4 成為了沒有前驅的頂點，輸出頂點 4，刪除掉它和頂點 3 和 5 的有向邊。
4. 然后，頂點 3 沒有了前驅，輸出它，并刪除它與 5 的有向邊。
5. 最后，頂點 5 沒有前驅，輸出它，于是得出最后的結果為：1，2，4，3，5。
一般來說，一個有向無環圖可以有一個或多個拓撲排序的序列。
**代碼示例**
運用廣度優先搜索的方法對這個圖的結構進行遍歷。在構建這個圖的過程中，用一個鏈接矩陣 adj 來表示這個圖的結構，用一個 indegree 的數組統計每個頂點的入度，重點看如何實現拓撲排序。
```
void?sort()?{
????Queue<Integer>?q?=?new?LinkedList();?//?定義一個隊列?q
????//?將所有入度為?0?的頂點加入到隊列?q
????for?(int?v?=?0;?v?<?V;?v++)?{
????????if?(indegree[v]?==?0)?q.add(v);
????}
????//?循環，直到隊列為空
????while?(!q.isEmpty())?{
????????int?v?=?q.poll();
????????//?每次循環中，從隊列中取出頂點，即為按照入度數目排序中最小的那個頂點
????????print(v);
????????//?將跟這個頂點相連的其他頂點的入度減?1，如果發現那個頂點的入度變成了?0，將其加入到隊列的末尾
????????for?(int?u?=?0;?u?<?adj[v].length;?u++)?{
????????????if?(--indegree[u]?==?0)?{
????????????????q.add(u);
????????????}
????????}
????}
}
```
**算法分析**
時間復雜度
統計頂點的入度需要 O(n) 的時間，接下來每個頂點被遍歷一次，同樣需要 O(n) 的時間，所以拓撲排序的時間復雜度是 O(n)。
建議：利用深度優先搜索的方法對這道題實現拓撲排序。
* [ ] 結語
這節課復習了面試中經常會被考到的排序算法，最重點內容是歸并排序和快速排序。除了要好好理解它們的思路，還必須要能寫出沒有 bug 的代碼，因此建議多做 LeetCode 里面的經典題目。
