大家好，我是小风哥。今天给大家讲解一道很有意思的算法面试题，用非递归的形式写快速排序。其实这也会导致更多类似的问题，比如非递归二叉树的前序、中序、后序遍历等。这些问题背后的思路都是一样的，就是利用stack来手动模拟递归调用。道理很简单，是的，一句话就可以说清楚，但问题是你真的理解了吗？如何使用栈手动模拟递归调用？面对这个问题，你的大脑是否思路清晰？别着急，先从最简单的快速排开始吧。快速排序，快速排序想必大家都知道，我们以数组中的某个数作为基准，通常是数组的第一个或最后一个（当然其他选择方式也是可以的），这里假设是最后一个数组的元素为基准：然后把数组中比基准小的数放在左边，比基准大的数放在右边：这样处理后，基数放在得到最终位置和两个子数组：base左边的数组和base右边的数组，可以对这两个子数组进行同样的处理。这用代码表示：voidquick_sort(vector&arr,intb,inte){if(b>=e)return;整数i=b-1;对于(intk=b;k表示是哪一段要排序的数组，所以用pair来记录这个数组的开始和结束。由于我们需要使用堆栈来跟踪问题解决的顺序，因此我们最终将堆栈定义为：stack>tasks;万事俱备，是时候创建一些任务了，任务的来源是什么？很简单，就是数组本身：intsize=arr.size();tasks.push(pair(0,size-1));接下来是最重要的部分：while(!tasks.empty()){//取出栈顶元素//处理//是否有新的子任务需要入栈}整体框架是像这样，接下来的三个问题是：是否有新的取出栈顶元素的子任务子任务需要入栈，如果有则入栈。第一个问题很简单，没什么好说的；第二个问题是如何处理一个子任务，其实很简单，就是用base把数组分成两个子数组。第三个问题是重点。我们怎么知道是否有新的子任务需要入栈呢？想想这个问题。..如果用base划分数组后发现数组已经有序了，那么就不用再创建子任务了，因为当前数组已经有序了！否则我们需要创建子任务。因此，我们必须知道数组划分后是否已经排序。基于上面的讨论，我们可以这样实现分区函数：intpartition(vector&arr,intb,inte,bool*sorted){if(b>e||b==e)return-1;整数i=b-1;for(intj=b;j(p+1,top.second));tasks.push(pair(top.first,p-1));}分析完所有问题，完整代码为：voidquick_sort(vector&arr){intsize=arr.size();如果（大小==0||大小==1）返回；堆栈<对>任务；tasks.push(pair(0,size-1));整数b=0;while(!tasks.empty()){autotop=tasks.top();任务.pop();布尔排序=真；intp=partition(arr,top.first,top.second,&sorted);如果（已排序）{继续；}else{tasks.push(pair(p+1,top.second));tasks.push(pair(top.first,p-1));}}}运行它，它像魔术一样工作，没有！这段代码是如何工作的？不，这根本不是魔术，让我们仔细看看这段代码是如何工作的。假设当前栈顶元素为(2,9)，我们获取栈顶元素并弹出：此时我们需要对数组中下标为2到9的元素进行排序，并以末尾的底作为基准进行划分：假设划分后底放在下标5处，得到两个子问题(2,3)和(4,9)：划分完底后判断即数组是无序的（分区函数中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)时会从栈中弹出，而递归版本不会弹出退出栈帧quick_sort(2,9)，函数quick_sort(2,3)执行完后，会返回函数quick_sort(2,9)，然后调用函数quick_sort(4,9)。非递归实现之所以能将子任务(2,9)提前出栈，是因为递归版本的所有递归调用都位于函数的末尾，也就是所谓的“尾递归”.尾递归是一种比较常见的现象，二叉树的前序遍历的递归实现也是如此：voidtree_travel(Tree*t){if(t){print(t->value);tree_travel(t->left);tree_travel(t->right);}}你可以使用与本文相同的套路将上面的递归代码转换为非递归代码，但是二叉树的中序遍历或后序遍历呢？voidtree_travel(Tree*t){if(t){tree_travel(t->left);打印（t->值）；tree_travel（t->右）；}}此时，本文讲解的套路就失效了，所以我们需要一个更通用的方法，将这种非尾递归代码转化为递归代码，这个通用方法是什么？我希望这篇文章能帮助你理解递归、堆栈和快速排序。
