在之前的文章當中，我們通過海盜分金幣問題詳細講解了遞歸方法。
我們可以認為在遞歸的過程當中，我們通過函數自己調用自己，將大問題轉化成了小問題，因此簡化了編碼以及建模。今天這篇文章呢，就正式和大家聊一聊將大問題簡化成小問題的分治算法的經典使用場景——排序。
排序算法
排序算法有很多，很多博文都有總結，號稱有十大經典的排序算法。我們信手拈來就可以說上來很多，比如插入排序、選擇排序、桶排序、希爾排序、快速排序、歸併排序等等。老實講這麼多排序算法，但我們實際工作中並不會用到那麼多，凡是高級語言都有自帶的排序工具，我們直接調用就好。為了應付面試以及提升自己算法能力呢，用到的也就那麼幾種。今天我們來介紹一下利用分治思想實現的兩種經典排序算法——歸併排序與快速排序。
歸併排序
我們先來講歸併排序，歸併排序的思路其實很簡單，說白了只有一句話：兩個有序數組歸併的複雜度是 O(n) 。
我們舉個例子：
<code>a = [1, 4, 6]b = [2, 4, 5]c = []/<code>
我們用i和j分別表示a和b兩個數組的下標，c表示歸併之後的數組，顯然一開始的時候i, j = 0, 0。我們不停地比較a和b數組i和j位置大小關係，將小的那個數填入c。
填入一個數之後：
<code>i = 1j = 0a = [1, 4, 6]b = [2, 4, 5]c = [1]/<code>
填入兩個數之後：
<code>i = 1j = 1a = [1, 4, 6]b = [2, 4, 5]c = [1, 2]/<code>
我們重複以上步驟，直到a和b數組當中所有的數都填入c數組為止，我們可以很方便地寫出以上操作的代碼：
從上面的代碼我們也能看出來，這個過程雖然簡單，但是寫成代碼非常麻煩，因為我們需要判斷數組是否已經全部填入的情況。這裡有一個簡化代碼的優化，就是在a和b兩個數組當中插入一個”標兵“，這個標兵設置成正無窮大的數，這樣當a數組當中其他元素都彈出之後。由於標兵大於b數組當中除了標兵之外其他所有的數，就可以保證a數組永遠不會越界，如此就可以簡化很多代碼了（前提，a和b數組當中不存在和標兵一樣大的數）。
我們來看代碼：
這裡應該都沒有問題，接下來的問題是我們怎麼利用歸併數組的操作來排序呢？
其實很簡單，這也是歸併排序的精髓。
我們每次將一個數組一分為二，顯然，這個劃分出來的數組不一定是有序的。但如果我們繼續切分呢？直到數組當中只有一個元素的時候，是不是就天然有序了呢？
我們舉個例子：
<code> [4, 1, 3, 2] / \\ [4, 1] [3, 2] / \\ / \\ [4] [1] [3] [2] \\ / \\ / [1, 4] [2, 3] \\ / [1, 2, 3, 4]/<code>
通過上面的這個過程我們可以發現，在歸併排序的時候，我們先一直往下遞歸切分數組，直到所有的切片當中只有一個元素天然有序。接著一層一層地歸併回來，當所有元素歸併結束的時候，數組就完成了排序。這也就是歸併排序的全部過程。
如果還不理解，還可以參考一下下面的動圖。
我們來試著用代碼來實現。之前我曾經在面試的時候被要求在白板上寫過歸併排序，當時我用的C++覺得編碼還有一定的難度。現在，當我用習慣了Python之後，我感覺編碼難度降低了很多。因為Python支持許多
數組相關的高級操作，比如切片，變長等等。整個歸併排序的代碼不超過20行，我們一起來看下代碼：
你看，無論是思想還是代碼實現，歸併排序並不難，就算一開始不熟悉，寫個兩遍也一定沒問題了。
理解了歸併排序之後，再來學快速排序就不難了，我們一起來看快速排序的算法原理。
快速排序
快速排序同樣利用了分治的思想，我們每次做一個小的操作，讓數組的一部分變得有序，之後我們通過遞歸，將這些有序的部分組合在一起，達到整體有序。
在歸併排序當中，我們劃分問題的方法是橫向切分，我們直接將數組一分為二，針對這兩個部分分別排序。快排稍稍不同，它並不是針對數組的橫向切分，而是從問題本身出發的”縱向“切分。在快速排序當中，我們解決的子問題不是對數組的一部分排序，而是提升數組的有序程度。怎麼提升呢？
我們在數組當中尋找一個數，作為標杆，我們利用這個標杆調整數組當中元素的順序。將小於它的放到它的左側，大於它的放到它的右側。這麼一個操作結束之後，可以肯定的是，這個標杆所在的位置就是排序完成之後，它應該在的位置。
我們來看個例子：
a = [8, 4, 3, 9, 10, 2, 7]
我們選擇7作為標杆，一輪操作之後可以得到：
a = [2, 4, 3, 7, 9, 10, 8]
接著我們怎麼做呢？很簡單，我們只需要對標杆前面以及標杆後面的部分遞歸調用重複上述操作即可。如果還不明白的同學可以看一下下面這張動圖：
如果用C++寫過快排的同學肯定對於快排的代碼印象深刻，它是屬於典型的原理不難，但是寫起來很麻煩的算法。因為快速排序需要用到兩個下標，寫的時候一不小心很容易寫出bug。同樣，由於Python當中動態數組的支持非常好，我們可以避免使用下標來實現快排，這樣代碼的可讀性以及編碼難度都要降低很多。
多說無益，我們來看代碼：
整個代碼除去註釋，不到15行，我想大家應該都非常容易理解。
最後，我們來分析一下這兩個算法的複雜度，為什麼說這兩個算法都是 O(nlogn) 的算法呢？（不考慮快速排序最差情況）這個證明非常簡單，我們放一張圖大家一看就明白了：
我們在遞歸的過程當中，我們只遍歷了一遍數組，雖然我們每一層都會講數組拆分。但是在遞歸樹上同一層的遞歸函數遍歷的總數加起來應該是等於數組的總長也就是n的。
而且遞歸的層數是有限制的，因為我們每次都將數組一分為二。而一個數組的最小長度是1，也就是說極端情況下我們一共能有 log2n 層，每一層的複雜度總和是n，所以整體的複雜度是 nlogn。
當然對於快速排序算法來說，如果數組是倒序的，我們默認取最後一個元素作為標杆的話，我們是無法切分數組的，因為除它之外所有的元素都比它大。在這種情況下算法的複雜度會退化到 n^2 。所以我們說快速排序算法最差複雜度是 n^2 。
到這裡，關於歸併排序與快速排序的算法就講完了。這兩個算法並不難，我想學過算法和數據結構的同學應該都有印象，但是在實際面試當中，真正能把代碼寫出來並且沒有明顯bug的實在是不多。我想，不論之前是否已經學會了，回顧一下都是很有必要的吧。
今天的文章就到這裡，希望大家有所收穫。如果喜歡本文，請順手點個關注吧。
閱讀更多 承志的算法課堂 的文章
