QuickSort 优化后的快速排序算法

1.优化选取枢轴

防止在第一次循环后，整个序列没有实质性的变化，如例子中的序列，则采用三数取中法（median-of-three）。即取三个关键字先进行排序，将蹭数作为枢轴，一般是取左端、右端和中间三个数，也可以随机选取。也有九数取中（median-of-nine）。

优化代码块如下：

int Partition(int *p, int low, int high){int pivotkey;//以下代码是增加的对选取枢轴的优化int m = low + (high - low) / 2;//计算数组中间的元素的下标if (*(p + low) > *(p + high)){//以下3个if语句是为了保证，在low,m,high三个下标中，使得*(p+low)的值最小swap(*(p + low), *(p + high));}if (*(p + m) > *(p + high)){swap(*(p + m), *(p + high));}if (*(p + m) > *(p + low)){swap(*(p + m), *(p + low));}//以下代码是增加的对选取枢轴的优化pivotkey = *(p + low);//设置传进来的数组中第一个数为枢轴变量while (low < high){while (low < high&&*(p + high) >= pivotkey){//如果low<high,且*(p+high)>=枢轴变量，则--high--high;}swap(*(p + low), *(p + high));//交换值while (low < high&&*(p + low) <= pivotkey){++low;}swap(*(p + low), *(p + high)); }return low;//返回枢轴}

2.优化不必要的交换

在进行循环时，可以先将枢轴值保存起来，将交换改为赋值

优化代码块如下：

int Partition(int *p, int low, int high){int pivotkey;pivotkey = *(p + low);//设置传进来的数组中第一个数为枢轴变量int tmp;//来保存枢轴变量tmp = pivotkey;while (low < high){while (low < high&&*(p + high) >= pivotkey){//如果low<high,且*(p+high)>=枢轴变量，则--high--high;}*(p + low) = *(p + high);//采用替换面不是交换的方式进行操作while (low < high&&*(p + low) <= pivotkey){++low;}*(p + high) = *(p + low);//采用替换面不是交换的方式进行操作}*(p + low) = tmp;//将枢轴数值替换给*(p+low)return low;//返回枢轴}

3.优化小数组时的排序方案

在数组元素个数小于50时，可以选择直接用插入排序，这样就能保证最大化地利用两种排序的优势来完成排序工作。

优化代码块如下：

#define MAX_LENGTH_INSERT_SORT 50//设置一个分界点void QSort(int *p,int low,int high){int pivot;//设置枢轴，即在这个位置，它左边的值比它小，右边的值比它大if (low < high&&(high-low)>MAX_LENGTH_INSERT_SORT){//如果数组元素个数大于50，采用快速排序pivot = Partition(p+low, 0, high-low);//用来初步排序QSort(p+low, 0, pivot -1-low);//递归调用自己，这里传的p+low，是新截断数组第一个位置的指针，所以后面的要用0t pivot-1-lowQSort(p + pivot + 1, 0, high - pivot - 1);}else{//否则采用插入排序InsertSort(a)}}

4.优化递归操作

实际代码就不上了，改的时间有bug。。。