数据结构：快速排序优化思路

首先快排的平均时间复杂度 优于很多排序，但是时间复杂度也有和他一样的，也就是堆排序，但为什么实际应用中快排要好于堆排呢？

原因主要有三个：

• 虽然都是 级别，但是时间复杂度是近似得到的，快排前面的系数更小，所以性能更好些。
• 堆排比较交换次数更多。因为快排是枢轴（pivot）左边的元素都比pivot小，右边的元素都更大，比较交换次数会比堆排更少些。
• 第三个原因也是最主要的原因，和CPU缓存（cache）有关。CPU有一块高速缓存区（cache）。堆 排序 要经常处理距离很远的数，不符合局部性原理，会导致cache命中率降低，频繁读写内存。

快排还能再快？

答案是肯定的，可以说在多数情况下，基本的快排速度是优于其他排序的，但是凡事都有局限性，快速排序对于数据不平衡的数组，重复数组，小数组等情况速度是比较不理想的，这个时候自然就需要优化，来尽可能的减小局限性。

如何优化

对寻找枢轴的方法进行优化

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

三数取中：

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

/*函数作用：取待排序序列中low、mid、high三个位置上数据，选取他们中间的那个数据作为枢轴*/
int PickMiddle(int arr[],int low,int high)
{
	int mid = (high+low) / 2;//计算数组中间的元素的下标
 
	//使用三数取中法选择枢轴
	if (arr[low] > arr[high])
		sawp(arr,low,high);	//目标: arr[low] <= arr[high]
	if (arr[mid] > arr[high])
		sawp(arr,mid,high);	//目标: arr[mid] <= arr[high]
							//以上两步保证把最大的移到最右端 
	if (arr[mid] > arr[low]) 
		sawp(arr,mid,low);	//目标: arr[low] >= arr[mid]
	//此时，arr[mid] <= arr[low] <= arr[high]
	
	return arr[low];
	//low的位置上保存这三个位置中间的值
	//分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了
}
复制代码

小数组使用插入排序

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

if(high-low < 7)
{
	InsertSort(L);	//进行插入排序
	return;
}//else进行正常的快排
复制代码

三向切分思想

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

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

• 使得元素 的值均小于切分元素；
• 使得元素 的值均大于切分元素；
• 使得元素 的值均等于切分元素， 的元素还没被扫描，切分算法执行到 为止。

int QSort(int arr[],int low,int high)
{  
    if(low < high)
    {  
        int lt = low;	//low为枢轴位置
        int gt = high;
        int i=low+1; //low位置的元素为枢轴元素，所以用于比较的元素从low+1开始
        
        int temp = arr[low]; //将枢轴的元素储存到temp中
        
        while(i <= gt)
        {  
            if(arr[i] < temp) 	//小于枢轴元素的放在lt左边 
                sawp(arr,lt++,i++);  //即交换lt和i位置的元素，此时枢纽位置(lt)右移一位，i也因此右移
            else if(arr[i] > temp)  //大于枢轴元素的放在gt右边 
                sawp(arr,i,gt--);  //交换i和gt位置的元素，gt需要左移，i由于变为gt位置元素，所以不需要移动
            else 		//相等时，无需交换，只需把i右移一位
                i++; 
        }  
        //lt-gt的元素已经排定，只需对it左边和gt右边的元素进行递归求解
        QSort(arr,low,lt-1);  
        QSort(arr,gt+1,high);  
    }   
}  
复制代码

递归优化

我们知道快排是一个递归算法，而递归的问题是如果递归太深容易栈溢出。所以针对快排的优化，还有一个角度是对递归的优化。网上很多文章中都提到一个叫做尾递归优化的东西。

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

尾递归

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

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

所谓的“快排尾递归优化”真的是尾递归优化吗？

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

关键代码如下

void QSort(int arr[],int low,int high)  
{  
    int pivot;  //枢轴
    while(low<high)//直到把右半边数组划分成最多只有一个元素为止，就排完了！
    {  
        pivot=Partition(arr,low,high);  
        QSort(arr,low,pivot-1);  //对低子表递归排序
        low=pivot+1;  
    }  
}  
复制代码

首先上面代码中递归调用并不是最后一步，甚至最后一行都不是，和我们上面看到的尾递归的定义不太一样，我查阅了网上很多资料，其中算法导论中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），枢轴选取采用三数取中方式

普通双递归的递归树为：

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

不过这种优化我觉得没什么必要，毕竟这只是把递归算法转化为了迭代算法，而所有的递归都可以转化为迭代，为何又不把另一个递归写成迭代呢；更何况经过优化后快排的平均递归深度基本为 ，虽然可能为n，但这种情况在使用了各种优化后，几乎不可能出现了，所以我觉得优化算法，最重要的应该是结合具体情况对算法本身优化，而不是粗暴的把递归改成非递归。

参考文献：

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

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

Erlang学习：快速排序和尾递归