既然这是一篇主题思想为优化快排的文章，自然就不讨论关于快排的一些定义和基础性的问题，只说快排应该怎么优化。

我们知道基本的快速排序选取第一个或最后一个元素作为枢轴，但是，这一直很不好的处理方法。对于这个问题一般有两种处理方法：随机选取枢轴、三数取中（median-of-three）。

选三个数（或更多，一般为左中右）作为样本，取其中位数作为枢轴点，这样划分可以尽可能的使枢轴在中间，使两边数据更均衡。

对于很小和部分有序的数组，快排不如插排好。当待排序序列分割到一定长度后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排。

快速排序对于元素重复率特别高的数组，效率显得非常低下。举个例子，假如在排序过程中一个子数组已全部为重复元素，则对于此数组排序就应该停止了，但快排算法依然会将其切分为更小的数组。

一个简单的改进想法就是将数组分为三部分：小于当前切分元素的部分，等于当前切分元素的部分，大于当前切分元素的部分。用一张图说明就是这样：

为了更好的理解，得先了解了一下什么叫尾递归。

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

具体用法看这篇文章吧，我就不复述了。 尾调用优化 - 阮一峰的网络日志

了解完尾递归后，再来看看网上流行的快排尾递归优化方法。

关键代码如下

首先上面代码中递归调用并不是最后一步，甚至最后一行都不是，和我们上面看到的尾递归的定义不太一样，我查阅了网上很多资料，其中算法导论中7-4章也提到了这个问题。

算法导论中的题目：

中文版本：

原书中的问题是这样的：

The QUICKSORT algorithm of Section 7.1 contains two recursive calls to itself. After the call to PARTITION, the left subarray is recursively sorted and then the right subarray is recursively sorted. The second recursive call in QUICKSORT is not really necessary; it can be avoided by using an iterative control structure. This technique, called tail recursion, is provided automatically by good compilers. Consider the following version of quicksort, which simulates tail recursion.

这个问题也提到尾递归技术，但在后续的描述中更像是描述尾递归的思想，which simulates tail recursion这是书中的原话，意思也很明显，就是模拟尾递归技术，而非真正的尾递归。

那么用这样的方式到底能不能降低递归深度呢？

答案是能，不妨来画一下这两种方法的递归树：

首先设置模拟数组为（1,2,3,4,5,6,7,8,9,10,11），枢轴选取采用三数取中方式

普通双递归的递归树为：

而如果采用模拟尾递归的方法，由于去掉了高子表的递归，而采用直接调用快排处理函数；不难发现其实本质是相当于把右节点擦掉，把右节点的子节点直接连接到当前节点。这样右边的叶深度，也就是最大栈深度就下降了。这个是不需要依赖编译器优化的。

参考文献：

快速排序的优化 和关于递归的问题，说说我的想法

三种快速排序以及快速排序的优化