算法學習其實是一種學習和提高思維能力的過程。無論是在面試還是實際的工作和生活中，都會碰見一些從沒遇到過的問題
真正需要熟練掌握的排序算法應該是以下幾種：
1.基本的排序算法：冒泡排序（Bubble Sort）、插入排序（Insertion Sort）
2.?？嫉呐判蛩惴?歸并排序（Merge Sort）、快速排序（Quick Sort）、拓撲排序（Topological Sort）
3.其他排序算法：堆排序（Heap Sort）、桶排序（Bucket Sort)
下文將用10min結(jié)合例題和代碼針對排序算法進行探討。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?冒泡排序
1、基本思想
給定一個數(shù)組，把數(shù)組里的元素通通倒入到水池中，這些元素將通過相互之間的比較，按照大小順序一個一個地像氣泡一樣浮出水面。具體的實現(xiàn)方法就是：每一輪，從雜亂無章的數(shù)組頭部開始，每兩個元素比較大小并進行交換，直到這一輪當中最大或最小的元素被放置在數(shù)組的尾部，然后不斷地重復這個過程，直到所有元素都排好位置。元素相互比較的過程就是冒泡排序的核心操作。
01例題分析
給定數(shù)組 [2, 1, 7, 9, 5, 8]，要求按照從左到右、從小到大的順序進行排序。
解題思路：可以從左到右依次冒泡，把較大的數(shù)往右邊挪動即可。具體操作如動圖：
數(shù)組已經(jīng)排好序后。可以用算法在進行新一輪的比較中，判斷一下在上一輪比較的過程中有沒有發(fā)生兩兩交換，如果一次交換都沒有發(fā)生，就證明其實數(shù)組已經(jīng)排好序了。
2.代碼示例
冒泡排序的代碼如下：
a.首先我們定義了一個布爾變量hasChange，用來標記每輪遍歷中是否發(fā)生了交換。
b.在每輪遍歷開始的時候，將hasChange設(shè)置為false。
c.接下來，進行兩兩比較，如果發(fā)現(xiàn)當前的數(shù)比下一個數(shù)還大，那么就交換這兩個數(shù)，同時記錄一下有交換發(fā)生。
d.不斷地兩兩交換，直到在這一輪，把最大的數(shù)放置到數(shù)組的最末端。
3、算法分析
冒泡排序算法的空間和時間復雜度。假設(shè)數(shù)組的元素個數(shù)是n，由于在整個排序的過程中，是直接在給定的數(shù)組里面進行元素的兩兩交換，空間復雜度是O(1)。至于時間復雜度，有以下幾種情況：
a.給定的數(shù)組按照順序已經(jīng)排好
在這種情況下，只需要進行n - 1次的比較，兩兩交換次數(shù)為0，時間復雜度是O(n)，這是最好的情況。
b.給定的數(shù)組按照逆序排列
在這種情況下，需要進行n(n - 1) / 2次比較，時間復雜度是O(n^2)，這是最壞的情況。
c.給定的數(shù)組雜亂無章
在這種情況下，平均時間復雜度是O(n^2)
由此可見，冒泡排序的時間復雜度是O(n^2)，但它是一種穩(wěn)定的排序算法，所謂穩(wěn)定，也就是說如果數(shù)組里兩個相等的數(shù)，那么排序前后這兩個相等的數(shù)的相對位置保持不變。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 插入排序
1、算法思想
在冒泡排序中，經(jīng)過每一輪的排序處理后，數(shù)組后端的數(shù)是排好序的；而對于插入排序來說，經(jīng)過每一輪的排序處理后，數(shù)組前端的數(shù)都是排好序的。
插入排序的基本思想就是不斷地將尚未排好序的數(shù)插入到已經(jīng)排好序的部分。
02例題分析
對數(shù)組 [2, 1, 7, 9, 5, 8] 進行插入排序。
解題思路：將數(shù)組分成左右兩個部分，左邊是已經(jīng)排好序的部分，右邊是還沒有排好序的部分，剛開始，左邊已排好序的部分只有第一個元素2。接下來，我們對右邊的元素一個一個進行處理，將它們放到左邊。具體操作如下動圖：
2、代碼示例
a.首先，我們將數(shù)組的第一個元素看成是已經(jīng)排好序的部分，于是我們從第二個元素開始，即i從1開始遍歷數(shù)組。
b.每次在外圍循環(huán)開始的時候，把當前i 指向的值用current保存起來，以便將來把它插入到合適的位置。
c.接下來，利用指針j進行內(nèi)循環(huán)，不斷地拿它和current值進行比較，如果發(fā)現(xiàn)j所指向的值比current值大，那么就把這個數(shù)往右移動一位。
d.當內(nèi)循環(huán)結(jié)束后，j + 1所指向的位置就是我們要把current值插入的位置了。
最后不斷地重復，直到所有的數(shù)都排好。
3、算法分析
插入排序算法的空間和時間復雜度分析如下。
假設(shè)數(shù)組的元素個數(shù)是n，由于在整個排序的過程中，直接在給定的數(shù)組里面進行元素的兩兩交換，空間復雜度是O(1)。至于時間復雜度，有以下幾種情況：
a.給定的數(shù)組按照順序已經(jīng)排好
在這種情況下，我們只需要進行n - 1次的比較，兩兩交換次數(shù)為0，時間復雜度是O(n)，這是最好的情況。
b.給定的數(shù)組按照逆序排列
在這種情況下，我們需要進行n(n - 1) / 2次比較，時間復雜度是O(n^2)，這是最壞的情況。
c.給定的數(shù)組雜亂無章
在這種情況下，平均時間復雜度是O(n^2)
由此可見，和冒泡排序一樣，插入排序的時間復雜度是O(n^2)，并且它也是一種穩(wěn)定的排序算法。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?歸并排序
1、算法思想
歸并排序的核心思想是分治，所謂分治，就是把一個復雜的問題分成兩個或多個相同或相似的子問題，然后把子問題分成更小的子問題，直到子問題可以簡單的直接求解，最原問題的解就是子問題解的合并。
可以說，歸并排序?qū)⒎种蔚乃枷塍w現(xiàn)得淋漓盡致。歸并排序的思路就是，一開始先把數(shù)組從中間劃分成兩個子數(shù)組，一直遞歸地把子數(shù)組劃分成更小的子數(shù)組，直到子
數(shù)組里面只有一個元素，這個時候才開始排序，排序的方法就是按照大小順序合并兩個元素，接著依次按照遞歸的返回順序，不斷地合并排好序的子數(shù)組，直到最后
把整個數(shù)組的順序排好。
2、代碼示例
讓我們看看如何寫歸并排序的代碼，首先看看排序的主體函數(shù)：
主體函數(shù)非常簡潔：
1.首先判斷是不是只剩下最后一個元素了。
2.接著從中間將數(shù)組分成兩個部分。
3.接下來，分別遞歸地將左右兩半排好序。
4.最后將排好序的左右兩半合并起來。
接下來看看如何實現(xiàn)歸并操作：?
歸并操作很容易理解。
首先復制一份原來的數(shù)組，之所以要這樣做，是因為我們不僅要比較左右兩半的數(shù)據(jù)，而且要修改原來的數(shù)組，如果不復制原來的數(shù)組直接進行修改，那么會導致將來的比較出現(xiàn)錯誤。
接下來，定義一個k指針表示從什么位置開始修改原來的數(shù)組，i指針表示左半邊的起始位置，j表示右半邊的起始位置。
在接下來的比較中，一共可能會出現(xiàn)四種情況：
1.左半邊的數(shù)都處理完畢了，只剩下了右半邊的數(shù)，我們只需要將右半邊的數(shù)逐個拷貝過去就好。
2.右半邊的數(shù)都處理完畢了，只剩下了左半邊的數(shù)，我們只需要將左半邊的數(shù)逐個拷貝過去就好。
3.右邊的數(shù)小于左邊的數(shù)，我們將右邊的數(shù)拷貝到合適的位置，j指針往前移動一位。
4.左邊的數(shù)小于右邊的數(shù)，我們將左邊的數(shù)拷貝到合適的位置，i指針往前移動一位。
03例題分析
利用歸并排序算法對數(shù)組[2, 1, 7, 9, 5, 8]進行排序。首先不斷地對數(shù)組進行切分，直到各個子數(shù)組里只包含一個元素。演示如下圖：
合并能成功，先決條件必須是兩個子數(shù)組都已經(jīng)分別排好序了。
3、算法分析
歸并算法是一個不斷遞歸的過程，假設(shè)數(shù)組的元素個數(shù)是n，時間復雜度是T(n)的函數(shù)。把這個規(guī)模為n的問題分成兩個規(guī)模分別為n/2的子問題，每個子問題的時間復雜度就是T(n/2)，那么兩個子問題的復雜度就是2*T(n/2)，當兩個子問題都得到了解決，即兩個子數(shù)組都排好了序，就需要將它們合并，合并的復雜度是多少呢？很簡單，一共有n個元素，每次都要進行最多n-1次的比較，所以合并的復雜度是O(n)，由此我們得到了如下的遞歸復雜度公式：
T(n) = 2*T(n/2) + O(n)
怎么解這個公式呢？需要不斷地把一個規(guī)模為n的問題分解成規(guī)模為n/2的問題，一直分解到規(guī)模大小為1，如果n等于2，我們只需要分一次，如果n等于4，則需要分2次，這里的次數(shù)是按照規(guī)模大小的變化分類的：
以此類推，對于規(guī)模為n的問題，一共要進行l(wèi)og(n)層的大小切分。在每一層里，都要進行合并，所涉及到的元素其實就是數(shù)組里的所有元素，因此，每一層的合并復雜度都是O(n)，所以整體的復雜度就是O(nlogn)。
對于空間復雜度，由于合并n個元素需要分配一個大小為n的額外數(shù)組，合并完成之后，這個數(shù)組的空間就會被釋放，所以算法的空間復雜度就是O(n)。最后，歸并排序也是穩(wěn)定的排序算法。
歸并算法的思想很重要，其中對兩個有序數(shù)組合并的操作，在很多面試題里都有用到。建議大家一定要把這個算法練熟。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 快速排序
1、算法思想
快速排序也采用了分治的思想，策略就是：把原始的數(shù)組篩選成較小和較大的兩個子數(shù)組，然后遞歸地排序兩個子數(shù)組。
如，現(xiàn)在要把班里的所有同學按照高矮順序排成一排。老師先隨機地挑選了同學A，讓所有其他同學和A比高矮，比A矮的都站在A的左邊，比A高的都站在A的右邊。接下來，老師分別從左邊和右邊的同學里選擇了同學B和C，然后不斷地篩選和排列下去。
在分成較小和較大的兩個子數(shù)組過程中，如何選定一個基準值（也就是同學A、B、C等）尤為關(guān)鍵。下面讓我們通過例題來深入理解快速排序算法。
04例題分析
再對數(shù)組[2, 1, 7, 9,?5, 8]進行排序，按照快速排序的思想
解題思路：首先把數(shù)組篩選成較小和較大的兩個子數(shù)組，隨機從數(shù)組里選取一個數(shù)作為基準值，比如7好了，于是原始的數(shù)組就被分成了如下兩個子數(shù)組：
這里需要注意的是，快速排序是直接在原始數(shù)組里進行各種交換操作，所以當子數(shù)組被分割出來的時候，原始數(shù)組里的排列也被改變了。
接下來，在較小的子數(shù)組里選2作為基準值，在較大的子數(shù)組里選8作為基準值，繼續(xù)分割子數(shù)組。
繼續(xù)將元素個數(shù)大于1的子數(shù)組進行劃分，得到：
可以看到，當所有子數(shù)組里的元素個數(shù)都為1的時候，原始數(shù)組也被排好序了。
2、代碼示例
先是主體函數(shù)：
主函數(shù)非常簡潔：
1.首先判斷是否只剩下了一個元素，如果是，就不需要排序了，直接返回。
2.接著，利用partition函數(shù)找到一個隨機的基準點。這個時候，基準點左邊的數(shù)一定都小于基準值，而右邊的數(shù)一定都大于基準值。
3.遞歸地對基準點左半邊和右半邊的數(shù)進行排序。
接下來看如何實現(xiàn)partition函數(shù)獲得基準值，并將數(shù)組劃分好。
1.首先，為了避免最糟糕的情況出現(xiàn)，我們隨機地選擇一個數(shù)作為基準值，將它放置到最右邊，也就是hi指針的位置，所以，nums[hi]就是我們的基準值。
2.接著，從左到右不斷地拿每個數(shù)和基準值比較，如果發(fā)現(xiàn)當前的數(shù)比基準值小，就將它放到指針i所指向的位置。循環(huán)完畢后，i指針之前的數(shù)都比基準值小。
3.最后將一開始放置在末尾的基準值放置到指針i的位置，這樣一來，i 指針之后的數(shù)都比基準值大了。
4.返回指針i，作為基準點的位置。
3、算法分析
在解這道例題的過程中，被選出來的基準值都是當前子數(shù)組的中間數(shù)，這是快速排序的最佳情況，通過這樣的分割，能保證對于一個規(guī)模大小為n的問題，能被均勻分解成兩個規(guī)模大小為n/2的子問題，回顧一下，歸并排序也采用了相同的劃分方法。如此一來，快速排序在最優(yōu)情況下的算法時間復雜度就是:
T(n) = 2 * T(n/2) + O(n)
這個O(n)如何得出來的呢？在把規(guī)模大小為n的問題分解成n/2的兩個子問題時，需要判斷是不是和基準值進行了n-1次比較。而這n-1次比較的復雜度就是O(n)。很顯然，在最優(yōu)情況下，快速排序的復雜度也是O(nlogn)。
最壞的情況是如果我們每次在選擇基準值的時候，非常不幸運地選擇了子數(shù)組里的最大或者最小值，也就是說每次都把子數(shù)組分成了兩個更小的子數(shù)組，其中一個的長度為1，另外一個的長度只比原子數(shù)組少1。例如，對于數(shù)組來說，每次我們挑選的基準值分別是9,
8, 7, 5, 2的時候，我們的劃分過程就變成了這樣：
這其實和冒泡排序的過程類似了，意味著快速排序在最壞的情況下算法復雜度也變?yōu)榱薕(n^2)?？梢酝ㄟ^隨機地選取基準值就可以避免出現(xiàn)最壞的情況了。
空間復雜度，和歸并排序不同，快速排序在每次遞歸的過程中，只需要開辟O(1)的存儲空間來完成交換操作實現(xiàn)直接對數(shù)組的修改，又因為遞歸次數(shù)為logn，所以它的整體空間復雜度完全取決于壓堆棧的次數(shù)，因此它的空間復雜度是O(logn)。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 拓撲排序
和前面介紹的幾種排序不同，拓撲排序應用的場合不再是一個簡單的數(shù)組，拓撲是一種研究，它研究的是圖論里面頂點和頂點連線之間的性質(zhì)。拓撲排序就是要將這些頂點按照相連的性質(zhì)進行排序。要能實現(xiàn)拓撲排序，得有幾個前提：
1.首先這個圖必須是有向圖
2.圖里面沒有環(huán)
拓撲排序一般用來理清具有依賴關(guān)系的任務(wù)。舉個最簡單的例子，假設(shè)有三門課程A、B、C，如果想要學習課程C就必須先把課程B學完，要學習課程B，還得先學習課程A，所以得出課程的學習順序應該是A -> B -> C。
1、算法思想
首先將問題用一個有向無環(huán)圖（DAG, Directed Acyclic Graph）進行抽象表達，定義出哪些是圖的頂點，頂點之間如何互相關(guān)聯(lián)。接下來，可以利用廣度優(yōu)先搜索或深度優(yōu)先搜索來進行拓撲排序。
利用廣度優(yōu)先搜索的思想比較直觀易懂，下面我們就以一道簡單的例題來學習如何對一個有向無環(huán)圖進行拓撲排序。
05例題分析
有一個學生想要修完5門課程的學分，這5門課程分別用1、2、3、4、5來表示，現(xiàn)在已知學習這些課程有如下的要求：
1.課程2和4依賴于課程1
2.課程3依賴于課程2和4
3.課程4依賴于課程1和2
4.課程5依賴于課程3和4
那么這個學生應該按照怎樣的順序來學習這5門課程呢？
解題思路：可以把5門課程看成是一個圖里的5個頂點，用有向線段按照它們的相互關(guān)系連起來，這個有向圖里沒有環(huán)，無論從哪個頂點出發(fā)，都不會再回到那個頂點。并且，這個圖里并沒有孤島的出現(xiàn)，因此，我們可以對它進行拓撲排序，具體事例如動圖：
一般來說，一個有向無環(huán)圖可以有一個或多個拓撲排序的序列。
2、代碼示例
在這里我們運用廣度優(yōu)先搜索的方法對這個圖的結(jié)構(gòu)進行遍歷。在構(gòu)建這個圖的過程中，我們用一個鏈接矩陣adj來表示這個圖的結(jié)構(gòu)，用一個indegree的數(shù)組統(tǒng)計每個頂點的入度，由于篇幅有限，我們就不把具體的構(gòu)建過程寫出來了。我們這里重點看如何實現(xiàn)拓撲排序。
1.既然是要做廣度優(yōu)先搜索，我們一開始定義一個隊列q。
2.將所有入度為0的頂點加入到隊列q里。
3.不斷地循環(huán)，直到隊列為空。
4.在每次循環(huán)中，從隊列中取出頂點，這個就是按照入度數(shù)目排序中最小的那個頂點。
5.然后將跟這個頂點相連的其他頂點的入度減一，如果發(fā)現(xiàn)那個頂點的入度變成了0，將其加入到隊列的末尾，等待將來的處理。
3、算法分析
對于拓撲排序，統(tǒng)計頂點的入度需要O(n)的時間，接下來每個頂點被遍歷一次，同樣需要O(n)的時間，所以拓撲排序的時間復雜度是O(n)。
建議你利用深度優(yōu)先搜索的方法對這道題實現(xiàn)拓撲排序。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 結(jié)語
在這些排序算法中，歸并排序和快速排序是最重要的知識點，除了要好好理解它們的思路，還必須要能寫出沒有bug的代碼才行，因此要在課后多加練習呀。LeeCode（力扣）里面有很多關(guān)于拓撲排序的經(jīng)典題目，強烈建議大家去試試。
