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

针对文章分析出的问题,本文讲一部分问题的解决方法

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

由分析排有序的时间复杂度可以看出:选取key的值很重要,如何提高排有序或接近有序数组的效率呢? 有两种方法:1.随机选key 2.三数取中(这两种方法能解决文章测试代码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_i
	while (left < right)
	{
        //......
    }
    //......
}

用文章的测试代码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快速排序消耗的时间

 优化前

优化后

注意:三数取中在数组有序或接近有序时速度比随机数快,可以用测试性能代码试试看

总结:随机选key和三数取中可以优化排有序数组的时间复杂度,使其小于N^2,加了优化几乎不会有最坏情况,因此时间复杂度为N*logN

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

左边做key,右边先走,相遇位置的值比arr[key]小,需要分类讨论,设排升序,设指针left从左向右找大,指针right从右向左走找小

情况1:right找到小,但left一直没有找到大,导致right和left相遇的位置的值比arr[key_i]要小

情况2:right找小没找到,一直左移,和left相遇,相遇的位置的值可能和arr[key_i]相等,也可能比arr[key_i]要小

同理可以推出:右边做key,左边先走,相遇位置的值比arr[key]大