三数取中选择枢轴优势还是很明显的，但是还是处理不了重复数组
优化1、当待排序序列的长度分割到一定大小后，使用插入排序。
原因：对于很小和部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排
截止范围：待排序序列长度N = 10，虽然在5~20之间任一截止范围都有可能产生类似的结果，这种做法也避免了一些有害的退化情形。摘自《数据结构与算法分析》Mark Allen Weiness 著
- if (high - low + 1 < 10)
- {
- InsertSort(arr,low,high);
- return;
- }
测试数据：
测试数据分析：针对随机数组，使用三数取中选择枢轴+插排，效率还是可以提高一点，真是针对已排序的数组，是没有任何用处的。因为待排序序列是已经有序的，那么每次划分只能使待排序序列减一。此时，插排是发挥不了作用的。所以这里看不到时间的减少。另外，三数取中选择枢轴+插排还是不能处理重复数组
优化2、在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割
举例：
待排序序列 1 4 6 7 6 6 7 6 8 6
三数取中选取枢轴：下标为4的数6
转换后，待分割序列：6 4 6 7 1 6 7 6 8 6
枢轴key：6
本次划分后，未对与key元素相等处理的结果：1 4 6 6 7 6 7 6 8 6
下次的两个子序列为：1 4 6 和 7 6 7 6 8 6
本次划分后，对与key元素相等处理的结果：1 4 6 6 6 6 6 7 8 7
下次的两个子序列为：1 4 和 7 8 7
经过对比，我们可以看出，在一次划分后，把与key相等的元素聚在一起，能减少迭代次数，效率会提高不少
具体过程：在处理过程中，会有两个步骤
第一步，在划分过程中，把与key相等元素放入数组的两端
第二步，划分结束后，把与key相等的元素移到枢轴周围
举例：
待排序序列 1 4 6 7 6 6 7 6 8 6
三数取中选取枢轴：下标为4的数6
转换后，待分割序列：6 4 6 7 1 6 7 6 8 6
枢轴key：6
第一步，在划分过程中，把与key相等元素放入数组的两端
结果为：6 4 1 6(枢轴) 7 8 7 6 6 6
此时，与6相等的元素全放入在两端了
第二步，划分结束后，把与key相等的元素移到枢轴周围
结果为：1 4 66(枢轴) 6 6 6 7 8 7
此时，与6相等的元素全移到枢轴周围了
之后，在1 4 和 7 8 7两个子序列进行快排
代码
void QSort(int arr[],int low,int high)
{
int first = low;
int last = high;
int left = low;
int right = high;
int leftLen = 0;
int rightLen = 0;
if (high - low + 1 < 10)
{
InsertSort(arr,low,high);
return;
}
//一次分割
int key = SelectPivotMedianOfThree(arr,low,high);//使用三数取中法选择枢轴
while(low < high)
{
while(high > low && arr[high] >= key)
{
if (arr[high] == key)//处理相等元素
{
swap(arr[right],arr[high]);
right--;
rightLen++;
}
high--;
}
arr[low] = arr[high];
while(high > low && arr[low] <= key)
{
if (arr[low] == key)
{
swap(arr[left],arr[low]);
left++;
leftLen++;
}
low++;
}
arr[high] = arr[low];
}
arr[low] = key;
//一次快排结束
//把与枢轴key相同的元素移到枢轴最终位置周围
int i = low - 1;
int j = first;
while(j < left && arr[i] != key)
{
swap(arr[i],arr[j]);
i--;
j++;
}
i = low + 1;
j = last;
while(j > right && arr[i] != key)
{
swap(arr[i],arr[j]);
i++;
j--;
}
QSort(arr,first,low - 1 - leftLen);
QSort(arr,low + 1 + rightLen,last);
}
测试数据：
测试数据分析：三数取中选择枢轴+插排+聚集相等元素的组合，效果竟然好的出奇。
原因：在数组中，如果有相等的元素，那么就可以减少不少冗余的划分。这点在重复数组中体现特别明显啊。
其实这里，插排的作用还是不怎么大的。
优化3：优化递归操作
快排函数在函数尾部有两次递归操作，我们可以对其使用尾递归优化
优点：如果待排序的序列划分极端不平衡，递归的深度将趋近于n，而栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提高性能。
代码：
- void QSort(int arr[],int low,int high)
- {
- int pivotPos = -1;
- if (high - low + 1 < 10)
- {
- InsertSort(arr,low,high);&