122.【C语言】数据结构之快速排序(Hoare排序的优化)

1.解决方法(即优化方法)

方法1.随机选key

运行结果

方法2:三数取中

1.含义

2.做法

3.代码

1.若arr[left] < arr[mid_i],则arr[right]可能的位置也有三处

2.若arr[left] > arr[mid_i],则arr[right]可能的位置也有三处

2.证明当key_i=left时,right先走,使left和right相遇的位置比arr[key_i]小

针对121.【C语言】数据结构之快速排序(未优化的Hoare排序存在的问题)以及时间复杂度的分析文章分析出的问题,本文讲一部分问题的解决方法

1.解决方法(即优化方法)

由分析排有序的时间复杂度可以看出:选取key的值很重要,如何提高排有序或接近有序数组的效率呢? 有两种方法:1.随机选key 2.三数取中(这两种方法能解决121.【C语言】数据结构之快速排序(未优化的Hoare排序存在的问题)以及时间复杂度的分析文章测试代码1和2的问题,但不能解决测试代码3产生的问题)

方法1.随机选key

key_i不一定初始为0,因此不在左侧,可以随机选key来提高排序的效率,但注意随机值的下标应该在区间[left,right]范围内

***则key_i=left+x(0≦x≦right-left)***

得出随机值的下标rand_i,但下方的循环是按照key_i=left设计的,因此需要交换arr[left]和arr[rand_i]位置来使arr[key_i]获得新的值

随机选key_i不一定每次选到最小或最大的,因此效率高

void QuickSort_Hoare(int* arr, int left, int right)
{if (left >= right)return;//单趟快速排序int begin = left;int end = right;srand((unsigned int)time(0));int rand_i = left+rand() % (right - left);Swap(&arr[left], &arr[rand_i]);//随机找一个值与左边交换int key_i = left;//最终还是左边做key_iwhile (left < right){//......}//......
}

用121.【C语言】数据结构之快速排序(未优化的Hoare排序存在的问题)以及时间复杂度的分析文章的测试代码1和测试代码2去测试含随机选key的Hoare快速排序

运行结果

正常运行

修改测试代码1的N为3000,看看优化前后的Hoare快速排序消耗的时间

优化前

优化后

方法2:三数取中

1.含义

三个数值取中间数值对应的下标

2.做法

设mid_i为left和right的中间值,在arr[left],arr[middle],arr[right]中取既不是最大也不是最小的数,显然需要两两比较

3.代码

先讨论arr[left]和arr[mid_i]的大小关系

1.若arr[left] < arr[mid_i],则arr[right]可能的位置也有三处

	if (arr[left] < arr[mid_i]){if (arr[right] > arr[mid_i]){int key_i = mid_i;}else if (arr[right] > arr[left]){int key_i = right;}else{int key_i = left;}}else{//......}

2.若arr[left] > arr[mid_i],则arr[right]可能的位置也有三处

	if (arr[left] < arr[mid_i]){//......}else{if (arr[right] > arr[left]){int key_i = left;}else if (arr[right] > arr[mid_i]){int key_i = right;}else{int key_i = mid_i;}}

写到函数里

int GetMiddleNum(int left,int right,int*arr)
{int mid_i = (left + right) / 2;if (arr[left] < arr[mid_i]){if (arr[right] > arr[mid_i]){return mid_i;}else if (arr[right] > arr[left]){return right;}else{return left;}}else{if (arr[right] > arr[left]){return left;}else if (arr[right] > arr[mid_i]){return right;}else{return mid_i;}}
}

优化后的Hoare快速排序写为

void QuickSort_Hoare(int* arr, int left, int right)
{if (left >= right)return;//单趟快速排序int begin = left;int end = right;int ret = GetMiddleNum(left, right, arr);if (left != ret)//避免left自己和自己交换{Swap(&arr[left], &arr[ret]);}int key_i = left;while (left < right){//......}//......
}

修改测试代码1的N为3000,看看优化前后的Hoare快速排序消耗的时间

优化前

优化后