以非遞歸的形式來寫快速排序

今天給大家講解一道非常有趣的算法面試題，以非遞歸的形式來寫快速排序。

其實這也可以衍生出更多同類問題，非遞歸二叉樹的前序、中序、后序遍歷等等，這些問題的背后的思想是一致的，那就是用棧來手動模擬遞歸調(diào)用。

道理很簡單有沒有，一句話就能說清楚，但問題是你真的理解了嗎？該怎樣用棧來手動模擬遞歸調(diào)用呢？你的大腦在面對這個問題時有一個清晰的思路嗎？

別著急，我們先從最簡單的快排開始。

快排，quick sort

快速排序想必大家都知道，我們以數(shù)組中的某個數(shù)字為基準(zhǔn)，通常是數(shù)組的第一個或者最后一個(當(dāng)然也可以是其它選擇方式)，這里假設(shè)以數(shù)組的最后一個元素為基準(zhǔn)：

然后將數(shù)組中小于該基準(zhǔn)的數(shù)字放在左邊、將大于該數(shù)字的放在右邊：

經(jīng)過這一次處理后base就被放到了最終的位置上并得到了兩個子數(shù)組：base左邊的數(shù)組和base右邊的數(shù)組，以同樣的方式處理這兩個子數(shù)組即可。

用代碼表示就是這樣：

voidquick_sort(vector&arr,intb,inte){
if(b>=e)return;
inti=b-1;
for(intk=b;k

	

	其中參數(shù)中的b和e表示begin和end，也就是范圍。

	可以看到，最終使用遞歸的方式編寫的代碼非常簡潔，也很容易理解，遞歸是計算機(jī)科學(xué)中一個極其重要的概念，遞歸對于理解編譯原理、編程語言、分而治之算法思想、排序以及動態(tài)規(guī)劃等等有重要的意義。

	遞歸版本很簡單有沒有，如果讓你用非遞歸的方式來實現(xiàn)呢？

	非遞歸手寫快速排序

	想一想這個問題！如果你真正理解遞歸的話那么就應(yīng)該能寫出來。

	我們再來看看這個遞歸寫法。

	首先會得到一個問題quick_sort(arr, b, e)，我們利用base進(jìn)行一次劃分后得到兩個子問題：

	quick_sort(arr, b, i - 1)

	quick_sort(arr, i + 1, e)

	在遞歸版本中這兩個子問題的狀態(tài)(所謂的狀態(tài)就是要解決哪個子問題，這里用參數(shù)中的begin和end來界定)是隨著函數(shù)的調(diào)用自動保存在棧幀中的，而我們需要用棧這種數(shù)據(jù)結(jié)構(gòu)來模擬這個過程。

	接下來，我們用變量task來表示要處理的子問題，也就是說入棧出棧的都是task，task可以這樣定義：

	
pair


	

	表示要對哪一段數(shù)組進(jìn)行排序，因此使用了pair來記錄這段數(shù)組的開始和結(jié)尾。

	由于需要使用棧來追蹤問題的解決順序，因此我們最終這樣定義棧：

	
stack>tasks;


	

	一切準(zhǔn)備就緒，是時候創(chuàng)建些任務(wù)了，任務(wù)的起源是什么呢？很簡單，就是數(shù)組本身：

	
intsize=arr.size();
tasks.push(pair(0,size-1));


	

	接下來就是最重要的部分了：

	
while(!tasks.empty()){
//取出棧頂元素
//處理
//是否有新的子任務(wù)需要push到棧中
}


	

	整體的框架就是這樣，接下來的三個問題就是：

	取出棧頂元素

	處理

	是否有新的子任務(wù)需要push到棧中，如果有則push到棧中

	第一個問題很簡單，沒什么可說的；第二個問題是說我們該怎樣處理一個子問題，其實也很簡單，就是用base將數(shù)組劃分為兩個子數(shù)組。

	第三個問題是重點，我們該怎么知道接下來是否有新的子任務(wù)需要push到棧中呢？

	想一想這個問題。。。

	如果用base對數(shù)組進(jìn)行劃分后發(fā)現(xiàn)數(shù)組已經(jīng)是有序的那么就沒有必要創(chuàng)建子任務(wù)了，因為當(dāng)前的數(shù)組已經(jīng)有序了嘛！否則我們就需要創(chuàng)建子任務(wù)。

	因此我們必須知道對數(shù)組進(jìn)行劃分后數(shù)組是不是已經(jīng)排好序。

	基于上述討論，我們可以這樣實現(xiàn)劃分函數(shù)partition：

	
intpartition(vector&arr,intb,inte,bool*sorted){
if(b>e||b==e)return-1;

inti=b-1;
for(intj=b;j

	

	這其實和開始遞歸版本中quick_sort函數(shù)里的劃分部分代碼沒什么區(qū)別，變化的部分僅在于我們將一次劃分后base所在的下標(biāo)以及判斷一次劃分后數(shù)組是否有序記錄在參數(shù)sorted中。

	一次劃分后如果sorted的值為true也就是數(shù)組已經(jīng)有序那么我們無需再創(chuàng)建新的子問題，一次劃分后我們得到兩個新的更小的子問題，即：

	
boolsorted=true;
intp=partition(arr,top.first,top.second,&sorted);

if(sorted){
continue;
}else{
tasks.push(pair(p+1,top.second));
tasks.push(pair(top.first,p-1));
}


	

	所有問題分析完畢，完整的代碼為：

	
voidquick_sort(vector&arr){
intsize=arr.size();
if(size==0||size==1)return;
stack>tasks;
tasks.push(pair(0,size-1));

intb=0;

while(!tasks.empty()){
autotop=tasks.top();
tasks.pop();

boolsorted=true;
intp=partition(arr,top.first,top.second,&sorted);

if(sorted){
continue;
}else{
tasks.push(pair(p+1,top.second));
tasks.push(pair(top.first,p-1));
}
}
}


	

	運行一下，it works like magic，有沒有！

	這段代碼是怎樣運行的？

	No，其實一點都不magic，接下來我們仔細(xì)看看這段代碼是怎么運行的。

	假設(shè)當(dāng)前棧頂元素為(2,9)，我們獲取棧頂元素，并將其從中pop掉：

	

	此時我們要對數(shù)組下標(biāo)2到9的元素進(jìn)行排序，把末尾的base作為基準(zhǔn)進(jìn)行劃分：

	

	假設(shè)劃分后base放到了下標(biāo)為5的位置，這樣我們得到了兩個子問題(2,3)以及(4,9)：

	

	由于經(jīng)過base的劃分后我們判斷出該數(shù)組不是有序的(partition函數(shù)中sorted參數(shù)的作用)，因此我們需要將兩個子問題(2,3)以及(4,9)放到棧中：

	

	就這樣，我們解決了子任務(wù)(2,9)，并得到了兩個更小的子問題(2,3)以及(4,9)，接著while循環(huán)繼續(xù)從棧中彈出任務(wù)并重復(fù)上述過程，當(dāng)棧為空時我們一定能確信數(shù)據(jù)已經(jīng)有序了。

	這個過程“完全”模擬了上述遞歸函數(shù)的調(diào)用，這里之所以加了引號，是因為我們的迭代快排版本進(jìn)行了一點點小小的優(yōu)化，這個優(yōu)化是什么呢？

	尾遞歸

	依然假設(shè)遞歸調(diào)用到函數(shù)quick_sort(2,9)，此時的函數(shù)棧幀為：

	

	基于base劃分后依然得到：

	

	根據(jù)遞歸版本的quick_sort實現(xiàn)接著我們需要調(diào)用quick_sort(2,3)，此時的棧幀為：

	

	看到非遞歸版本與遞歸版本的不同了吧：

	

	在非遞歸版本下，對處理子任務(wù)(2,9)時會將該任務(wù)從棧中pop出來，而遞歸版本則不會pop出quick_sort(2,9)的棧幀，函數(shù)quick_sort(2,3)執(zhí)行完后還會再次回到函數(shù)quick_sort(2,9)，然后接著調(diào)用函數(shù)quick_sort(4,9)。

	而之所以非遞歸實現(xiàn)可以提前將子任務(wù)(2,9)從棧中彈出是因為遞歸版本下所有遞歸調(diào)用都位于函數(shù)的末尾，這就是所謂的“尾遞歸”。

	尾遞歸是一種比較常見的現(xiàn)象，二叉樹的前序遍歷遞歸實現(xiàn)也是這樣：

	
voidtree_travel(Tree*t){
if(t){
print(t->value);
tree_travel(t->left);
tree_travel(t->right);
}
}


	

	你可以使用和本文一樣的套路將上述遞歸代碼轉(zhuǎn)為非遞歸代碼，但是如果是二叉樹的中序遍歷或者后序遍歷呢？

	
voidtree_travel(Tree*t){
if(t){
tree_travel(t->left);
print(t->value);
tree_travel(t->right);
}
}


	

	此時，本文中講解的套路就失效了，因此我們需要一種更加通用的方法將此類非尾遞歸代碼轉(zhuǎn)為遞歸代碼，這種通用的方法是什么呢？

	




	審核編輯：劉清