【hoare优化版】快速排序算法（2）

GitMidi三数取中

整体思想

图解分析

代码实现

Hoare优化

上篇我们介绍了hoare基础版，但是这种代码存在缺陷，所以我们提出了两种解决方案。主流的解决方案就是【三数取中选key】

GitMidi三数取中

在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。在此我们采用三数取中法，也就是取左端、中间、右端三个数的下标，然后进行排序，将中间数作为枢纽值。

取的三个数的中位数的下标
取的是下标❗
数值两两比较

整体思想

设置三个值下标：begin // end // midi
两个两个比较
得到中位数的下标

图解分析

【顺序序列优化前：等差数列O（N^2)】

【顺序序列优化后：类似二叉树等比数列O（N*logN)】

代码实现

//三数取中
int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] < a[end])
	{
		if (a[begin] > a[midi])
		{
			return begin;
		}
		else if(a[end]<a[midi])
		{
			return end;
		}
		else
		{
			return midi;
		}
	}
	else//begin>=end
	{
		if (a[midi] < a[end])
		{
			return end;
		}
		else if (a[midi] > a[begin])
		{
			return begin;
		}
		else
		{
			return midi;
		}
	}
}

Hoare优化

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//三数取中
int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] < a[end])
	{
		if (a[begin] > a[midi])
		{
			return begin;
		}
		else if(a[end]<a[midi])
		{
			return end;
		}
		else
		{
			return midi;
		}
	}
	else//begin>=end
	{
		if (a[midi] < a[end])
		{
			return end;
		}
		else if (a[midi] > a[begin])
		{
			return begin;
		}
		else
		{
			return midi;
		}
	}
}

//优化版本
int PartSort1(int* a, int begin, int end)//返回分割线
{
	int left = begin;
	int right = end;
	int keyi = begin;

	//三数取中
	int midi = GetMidi(a, begin, end);
	Swap(&a[keyi], &a[midi]);

	while (left < right)
	{
		//找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		//找到了
		Swap(&a[right], &a[left]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;
	return keyi;
	//分割 [begin,keyi-1] keyi [keyi+1,end]
}

void QuickSort(int* a, int begin,int end)
{
	if (begin >= end)//只有1个元素 没有区间
	{
		return;
	}
	int keyi = PartSort1(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}