大家好，我是小風哥。

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

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

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

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

快排，quick sort

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

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

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

用代碼表示就是這樣：

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);
}

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

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

非遞歸手寫快速排序

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

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

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

• quick_sort(arr, b, i - 1)
• quick_sort(arr, i + 1, e)

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

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

pair<int, int>

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

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

stack<pair<int, int>> tasks;

一切準備就緒，是時候創建些任務了，任務的起源是什么呢？很簡單，就是數組本身：

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

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

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

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

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

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

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

想一想這個問題。。。

如果用base對數組進行劃分后發現數組已經是有序的那么就沒有必要創建子任務了，因為當前的數組已經有序了嘛！否則我們就需要創建子任務。

因此我們必須知道對數組進行劃分后數組是不是已經排好序。

基于上述討論，我們可以這樣實現劃分函數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函數里的劃分部分代碼沒什么區別，變化的部分僅在于我們將一次劃分后base所在的下標以及判斷一次劃分后數組是否有序記錄在參數sorted中。

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

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，接下來我們仔細看看這段代碼是怎么運行的。

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

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

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

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

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

這個過程“完全”模擬了上述遞歸函數的調用，這里之所以加了引號，是因為我們的迭代快排版本進行了一點點小小的優化，這個優化是什么呢？

尾遞歸

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

基于base劃分后依然得到：

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

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

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

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

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

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

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

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

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

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