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。。。