快速排序(非遞歸)和歸並排序

我們知道，當快速排序的遞歸層次越多，那麼棧就有可能會溢出。那麼我們就需要寫一個非遞歸的。

1. 快速排序(非遞歸)

那麼我們怎麼把遞歸改成非遞歸的呢？
我們需要利用棧這個數據結構。
我們看下面的一組數據：

首先，我們將第一個元素的下標和最後一個元素的下標放到棧中：

然後，我們將9取出來放到right，將0取出來放到left裏，然後做單趟排序。
排完序是這個樣子：

然後，我們在將6的左區間和右區間有序該怎麼辦呢？我們將0和key-1入棧，然後將key+1和n-1入棧。

我們再出棧將9放到right，將6出棧放到left，再做單趟排序。
也就是6的右區間做單趟排序：

然後，我們再將9的左區間入棧，9的右區間入棧。
因為，9的右區間只有一個數不需要入棧，只入左區間。

然後，我們將7出棧放到right裏，將6出棧放到left裏。再做單趟排序：

此時，我們將8的左右區間入棧，8的左區間只有一個不入棧，8的右區間沒有也不入棧。此時，棧裏面還有0和4，也就是6的左區間，思路是一樣的。
完整代碼：

同樣道理，我們也可以用隊列來實現。

2. 歸並排序

2.1 基本思想

歸並排序是建立在歸並操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序錶合並成一個有序錶，稱為二路歸並。 歸並排序核心步驟：

動圖演示：

2.2 遞歸版本具體實現

其實我們就是將序列給分解成不能在分解的子問題。也就是只有1個或者沒有的時候，我們就可以開始合並了。
在合並的時候我們要額外開辟一個數組，因為如果在原數組合並，會把值給覆蓋。
首先，我們來看一下分解的代碼：

當begin和end都為0時，就返回，然後遞歸右區間，begin和end都為1時，返回。此時，我們就可以合並[0,0]和[1,1]兩個區間的值了。其它的道理類似。

那麼，在說一下如何合並：

我們以這組序列為例：
首先，我們需要將[0,0]和[1,1]合並，就是比較大小，小的先放到tmp數組裏，然後再繼續比較。當合並完之後，我們將tmp裏數據複制到原數組中。

這樣[0,1]區間就有序了，我們就開始合並[0,1]和[2,2]

這樣[0,2]就有序了，我們需要合並[3,3]和[4,4]

這樣[0,2]和[3,4]都有序了，我們需要合並[0,2]和[3,4]

這樣左區間就有序了，右區間也是同樣的道理。
完整代碼如下：

2.3 非遞歸版本具體實現

首先，我們看一下這組數據：

我們要歸的話，需要一個一個歸，10和6歸，7和1歸，3和9歸，4和2歸。
那麼我們就可以定義一個gap代錶要歸並的個數。
當gap為1時，也就是一個一個來合並。

然後，我們將gap為2，這樣就是兩兩合並。
也就是[0,1]和[2,3]合並，[4,5]和[6,7]合並。

然後就是四四合並，[0,3]和[4,7]合並。

從這裏，我們可以看出gap從1變成2然後變成4是2倍增長。
那麼我們就可以先控制gap了：

然後，我們需要控制數組下標了，我們可以定義一個i來控制，首先第一步是下標0和下標1合並，第二步是下標2和下標3合並…也就是i=0，i=2，i=4…
當兩兩合並時，[0,1]和[2,3]，[4,5]和[6,7]，也就是i=0，i=4，i=8…
那麼我們就可以控制下標了：

那麼這樣寫有沒有什麼問題呢？我們來看下面的數據：

如果gap為2時，也就是兩兩合並。[0,1]和[2,3]合並，[4,5]和[6,7]合並，[8,9]和[10,11]合並，但是[10,11]begin2和end2已經越界了。

當gap為4時，就是[0,3]和[4,7]合並，然後[8,11]和[12,15]合並。這時end1，begin，end2都越界了。

那麼我們就要想一下該如何去解决這個越界問題。
從上面的分析我們可以得出，end1，begin2，end2都可能會越界。所以這三個越界我們都需要控制。
在這裏分為三種情况：
第一種情况：end1沒越界，begin2沒越界，end2越界。那麼如果end2>=n時，我們就將end2賦值成n-1

第二種情况：end1沒越界，begin2越界，end2越界。那麼第二個區間就不存在，我們就要將第二個區間弄成一個不存在的區間

第三種情况：end1越界，那麼begin2，end2肯定也越界了。那麼我們需要將end1賦值成n-1，begin2和end2按照上面的再修改。

這樣就可以控制非遞歸的邊界問題了。完整代碼如下：

2.4 複雜度分析

2.4.1 時間複雜度

我們先說一下時間複雜度。

歸並排序分為分解和合並。首先分解我們可以看到它每次都是二次等分。一共n個數，每次都是二分，也就是2^x=n，x=logn。所以，分解有logn層。

合並其實和分解差不多，但合並需要排序，也就是每次合並都要過一遍n，然後有logn層，也就是n*logn。

所以時間複雜度就為logn+nlogn，在大O的漸進錶示法為O(nlogn)。

2.4.2 空間複雜度

空間複雜度就很簡單，我們可以看出它需要額外開辟n個數據的空間。然後我們要看它的遞歸深度，我們可以看出它遞歸有logn層，每次遞歸裏的空間是常數量，也就是O(1)，所以，空間複雜度就為n+logn，又因為n遠大於logn，所以空間複雜度為O(N)。

2.5 歸並排序的外排序

在我們說的這些常見的算法排序中，都能實現內排序。什麼是內排序呢？
內排序：就是數據存在內存中。下標隨機訪問，速度快。
但是，只有歸並排序才能做外排序。
那什麼是外排序呢？
外排序：數據元素太多不能同時放在內存中，而放在磁盤中，串行訪問，速度慢。

現在有這樣一個問題：
10億個整數文件，只給1G的運行內存，請對文件中的10億個數進行排序。
這個問題我們該如何解决呢？
首先，我們要知道10億個整數我們需要多少內存呢？
1G=1024MB，1024MB=10241024KB，1024KB=10241024*1024byte
所以1G大約等於10億字節。那麼10億個整數就是40億字節，差不多是4G。
解决方法：將文件分成4等分，每份為1G，分別讀到內存裏排序，排完序，再寫回磁盤小文件。然後再在磁盤裏歸並。