在之前的文章當中，我們通過海盜分金幣問題詳細講解了遞歸方法。

我們可以認為在遞歸的過程當中，我們通過函數自己調用自己，將大問題轉化成了小問題，因此簡化了編碼以及建模。今天這篇文章呢，就正式和大家聊一聊將大問題簡化成小問題的分治算法的經典使用場景——排序。

排序算法

排序算法有很多，很多博文都有總結，號稱有十大經典的排序算法。我們信手拈來就可以說上來很多，比如插入排序、選擇排序、桶排序、希爾排序、快速排序、歸并排序等等。老實講這么多排序算法，但我們實際工作中并不會用到那么多，凡是高級語言都有自帶的排序工具，我們直接調用就好。為了應付面試以及提升自己算法能力呢，用到的也就那么幾種。今天我們來介紹一下利用分治思想實現的兩種經典排序算法——歸并排序與快速排序。

歸并排序

我們先來講歸并排序，歸并排序的思路其實很簡單，說白了只有一句話：兩個有序數組歸并的復雜度是 O(n) 。

我們舉個例子：

a = [1, 4, 6]b = [2, 4, 5]c = []

我們用i和j分別表示a和b兩個數組的下標，c表示歸并之后的數組，顯然一開始的時候i, j = 0, 0。我們不停地比較a和b數組i和j位置大小關系，將小的那個數填入c。

填入一個數之后：

i = 1j = 0a = [1, 4, 6]b = [2, 4, 5]c = [1]

填入兩個數之后：

i = 1j = 1a = [1, 4, 6]b = [2, 4, 5]c = [1, 2]

我們重復以上步驟，直到a和b數組當中所有的數都填入c數組為止，我們可以很方便地寫出以上操作的代碼：

從上面的代碼我們也能看出來，這個過程雖然簡單，但是寫成代碼非常麻煩，因為我們需要判斷數組是否已經全部填入的情況。這里有一個簡化代碼的優化，就是在a和b兩個數組當中插入一個”標兵“，這個標兵設置成正無窮大的數，這樣當a數組當中其他元素都彈出之后。由于標兵大于b數組當中除了標兵之外其他所有的數，就可以保證a數組永遠不會越界，如此就可以簡化很多代碼了(前提，a和b數組當中不存在和標兵一樣大的數)。

我們來看代碼：

這里應該都沒有問題，接下來的問題是我們怎么利用歸并數組的操作來排序呢？

其實很簡單，這也是歸并排序的精髓。

我們每次將一個數組一分為二，顯然，這個劃分出來的數組不一定是有序的。但如果我們繼續切分呢？直到數組當中只有一個元素的時候，是不是就天然有序了呢？

我們舉個例子：

[4, 1, 3, 2] / [4, 1] [3, 2] / / [4] [1] [3] [2] / / [1, 4] [2, 3] / [1, 2, 3, 4]

通過上面的這個過程我們可以發現，在歸并排序的時候，我們先一直往下遞歸切分數組，直到所有的切片當中只有一個元素天然有序。接著一層一層地歸并回來，當所有元素歸并結束的時候，數組就完成了排序。這也就是歸并排序的全部過程。

如果還不理解，還可以參考一下下面的動圖。

我們來試著用代碼來實現。之前我曾經在面試的時候被要求在白板上寫過歸并排序，當時我用的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的實在是不多。我想，不論之前是否已經學會了，回顧一下都是很有必要的吧。

今天的文章就到這里，希望大家有所收獲。如果喜歡本文，請順手點個關注吧。

總結

以上是生活随笔為你收集整理的排序中减治法算法伪代码_算法浅谈——分治算法与归并、快速排序(附代码和动图演示)...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。