快速排序（2）——快速排序的优化

因为Hoare的快速排序写起来容易出错，并且有很多地方不太合适，于是，就有了一下几种优化。

基准值的优化

如果我们一直选取一组数据的第一个数据为基准值，如果遇到重复少的值的化，没什么问题。但是如果重复的值比较多的化，就会造成一些重复，使得程序运行速度减慢。因此，我们可以优化一下基准值的取值。最常见的方法就是取begin 、 end、 和begin end中位数这三个下标对应的数中不大也不小的值。

代码如下：

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

因此，我们更改一下快速排序

代码如下：

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	//注意一下
	int left = begin, right = end;

	int midi = GetMidi(a, begin, end);
	Swap(&midi, &begin);
	int keyi = begin;
	while (left < right)
	{
		//右边，找到比a[keyi]小的,然后放到左边
		//注意条件是<=
		while (left < right && a[keyi] <= a[right])
		{
			--right;
		}
		//左边，找到比a[keyi]大的，然后放到右边
		//注意条件是>=
		while (left < right && a[keyi] >= a[left])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	keyi = left;
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

挖坑法快速排序

挖坑法就是先将基准值存放在一个临时变量key中，形成一个坑位，然后右边找比key小的，然后放到原来的坑位，并且现在右边所处的位置形成一个新的坑位，然后左边开始找比key大的，然后找到后放到坑位，此时左边形成新的坑位，直到左右相遇。

图片实现

代码实现

int HoleSort(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int key = a[begin];
	int hole = begin;
	while (begin < end)
	{
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		a[hole] = a[end];
		hole = end;
		while (begin < end && a[begin] <= key)
		{

			++begin;
		}
		a[hole] = a[begin];
		hole = begin;
	}
	a[hole] = key;
	return hole;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = HoleSort(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

前后指针法快速排序

前后指针法就是有一个prev 和 cur 。开始时，prev指向基准值，cur指针指向prev后面的一个位置。开始时，先判断cur的值是否小于k，若小于，prve++，然后交换prve和cur，然后cur++。然后cur继续进行，当cur的值小于key，然后prve++，当prve的值大于key，然后交换prve和cur的值，然后cur++。直到cur越界。此时交换key和prve的值，并且令key=prve。

图片实现

代码实现

int PSort(int* a, int begin,int end)
{
	int prve =begin , cur = prve+1;
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int key = begin;
	while (cur <= end)
	{
		if (a[cur] <= a[key]&&++prve!=cur)
			Swap(&a[cur], &a[prve]);
		cur++;
	}
	Swap(&a[prve], &a[key]);
	key = prve;
	return key;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PSort(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}