大家好，我是小風哥。

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

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

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

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

快排，quick sort

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

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

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

用代碼表示就是這樣：

void quick_sort(vector<int>&arr, int b, int e) {
    if (b >= e) return;
    int i = b - 1;
    for (int k = b; k < e; k++)
        if (arr[k] < arr[e])
            swap(&arr[++i], &arr[k]);
    swap(&arr[++i], &arr[e]);
    
    quick_sort(arr, b, i - 1);
    quick_sort(arr, i + 1, e);
}

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

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

非遞歸手寫快速排序

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

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

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

• 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<int, int>

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

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

stack<pair<int, int>> tasks;

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

int size = arr.size();
tasks.push(pair<int, int>(0, size - 1));

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

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

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

• 取出棧頂元素
• 處理
• 是否有新的子任務(wù)需要push到棧中，如果有則push到棧中

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

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

想一想這個問題。。。

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

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

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

int partition(vector<int>&arr, int b, int e, bool* sorted) {
  if (b > e || b == e) return -1;

  int i = b - 1;
  for (int j = b; j < e; j++) {
    if (arr[j] < arr[e]) {
      *sorted = false;
      swap(arr[++i],arr[j]);
    }
  }
  swap(arr[++i], arr[e]);

  return i;
}

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

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

bool sorted = true;
    int p = partition(arr, top.first, top.second, &sorted);

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

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

void quick_sort(vector<int>&arr) {
  int size = arr.size();
  if (size == 0 || size == 1) return ;
  stack<pair<int,int>> tasks;
  tasks.push(pair<int,int>(0, size - 1));

  int b = 0;

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

    bool sorted = true;
    int p = partition(arr, top.first, top.second, &sorted);

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

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

這段代碼是怎樣運行的？

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

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

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

假設(shè)劃分后base放到了下標為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ù)上述過程，當棧為空時我們一定能確信數(shù)據(jù)已經(jīng)有序了。

這個過程“完全”模擬了上述遞歸函數(shù)的調(diào)用，這里之所以加了引號，是因為我們的迭代快排版本進行了一點點小小的優(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)也是這樣：

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

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

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

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

希望本篇對大家理解遞歸、棧、快排有所幫助。