提升还是不错的，但没有什么完美的东西，因为三数取中的“取”这一步又得花不少额外的时间。不过这一缺点可以被弥补一些，后面会讲使用插入排序。
尾递归优化
在快速排序的递归树中节点的信息是不需要被保存的，所以可以让一个父节点来代替其中一个孩子节点继续递归下去：
/***************************************
函数：尾递归优化版快速排序
功能：对[low, high)范围内的数据排序
期望运行时间：O(2nlgn)
***************************************/
void quickSortRoutine(int* low, int* high)
{
int range; ///区间元素个数
///当区间有不止1个元素时才进行分区
while((range = high - low) > 1) ///改为循环语句这样父节点就可以在下一次运算中充当孩子节点
{
int* pivot = hoarePartition(low, high, range); ///返回主元地址
quickSortRoutine(low, pivot); ///对左区间进行快速排序
low = pivot; ///注意区间范围
}
} 可以通过选择替代“较大”的孩子递归使得递归树的深度控制在lgn之内，不过快速排序本来就是靠概率吃饭的，这样会增加比较开销，我就不写了。 这里还有一点点优化的空间，那就是维护一个保存区间信息的数组，里面保存的数据为待分区的区间，这样就完全不用递归了。不过会额外增加空间上的消耗。
使“叶子”变粗
就像前面说的三数取中的花销很大，并且递归开销也很大，所以我们可以把快速排序的“触底”情况的限制放宽，最后对整个基本有序的数组应用插入排序。 于是得到完整快速排序：
#define FACTOR 37 ///叶子的宽度
/***************************************************************
函数：三数取中的霍尔分区算法
参数：对[low, high)范围内的数据分区，range为区间的元素个数
***************************************************************/
int* hoarePartition(int* low, int* high, int range)
{
///三数取中
int a = *((int)(((double)rand() / RAND_MAX) * range) + low);
int b = *((int)(((double)rand() / RAND_MAX) * range) + low);
int c = *((int)(((double)rand() / RAND_MAX) * range) + low);
int pivot = a > b ? (b > c ? b : (a > c ? c : a)) : (a > c ? a : (b > c ? c : b));
low--;
while(true)
{
while(*(++low) < pivot); ///扫描左区间
while(*(--high) > pivot); ///扫描右区间
///当两边都扫描到不属于自己区间的元素时
if(low < high)
{
///当两区间还没有交集说明有两个元素分别落在错误的区间，交换即可
int tmp = *low;
*low = *high;
*high = tmp;
}
///当区间相交时，Hoare分区只保证[0....pivot)中的元素 <= [pivot....n)中的元素
///并没有确定主元的位置，所以只得到两个确定大小关系的区间，中间没有主元相隔
else return low;
}
}
/***************************************
函数：尾递归优化版快速排序
功能：对[low, high)范围内的数据排序
期望运行时间：O(nlgn)
***************************************/
void quickSortRoutine(int* low, int* high)
{
int range; ///区间元素个数
///当区间有不止1个元素时才进行分区
while((range = high - low) > FACTOR) ///改为循环语句这样父节点就可以在下一次运算中充当孩子节点
{
int* pivot = hoarePartition(low, high, range); ///返回主元地址
quickSortRoutine(low, pivot); ///对左区间进行快速排序
low = pivot; ///注意区间范围
}
}
/********************************************************************
函数：优化一点点的插入排序
功能：对[low, high)内的数据进行排序
********************************************************************/
void improvedInsertionSort(int* low, int* high)
{
///因为最小值在第一位，所以直接从第三个元素开始插入
++low;
while(++low < high)
{
int tmp = *low; ///把待插入元素保存到临时变量中
int* destPos = low; ///计算插入位子
///把第一次测试单独提出来
if(*(--destPos) > tmp)
{
do
{
*(destPos + 1) = *destPos;
}while(*(--destPos) > tmp); ///测试上一个是否是目标位置
*(destPos + 1) = tmp; ///最后一次测试失败使得destPos比实际小1
}
}
}
/**********************************
函数：完整版快速排序
**********************************/
void quickSort(int* low, int* high)
{
///设置随机数种子
srand(time(nullptr));
///进行快速排序，叶子宽度为FACTOR
quickSortRoutine(low, high);
///找出最小值放到最开始作为插入排序的哨兵节点
int* minPos = low; ///最小值的位置
int* lastPos = low + FACTOR;
for(int* i = low + 1; i < lastPos; i++)
if(*i < *minPos) minPos = i;
int tmp = *low;
*low = *minPos;
*minPos = tmp;
///最后进行插入排序
improvedInsertionSort(low, high);
} 那么叶子的宽度该如何去选择呢。一般来说是8到20都不错，不过这里用了三数取中所以常数比普通随机选取主元的快速排序大，所以这里是个两位数就可以了。 上面那个37也是我主观选的，就像生活大爆炸里sheldon说：73是最美妙的数字，因为73是第21个素数，反过来37正好又是第12个素数，并且21正好又等于7和3的积， 另外把73转换为二进制后可以得到1001001，正读倒读都一样。感觉这样一写就很高端啊。
?
?