排序算法之六：快速排序（递归）

快速排序的基本思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法

其基本思想为：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
 if(right - left <= 1)
 return;
 
 // 按照基准值对array数组的 [left, right)区间中的元素进行划分
 int div = partion(array, left, right);
 
 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
 // 递归排[left, div)
 QuickSort(array, left, div);
 
 // 递归排[div+1, right)
 QuickSort(array, div+1, right);
}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

划分区间的常见方式

将区间按照基准值划分为左右两半部分的常见方式有三种，

1. hoare方法
2. 挖坑法
3. 前后指针法?

三种方法是排key左右区间的不同，整体快排的思想是递归?

1.hoare方法

https://img-blog.csdnimg.cn/07ddcfdc56874b2a9d12f585534ac87e.gif#pic_center

1.1图示

定义left和right来找大和找小

right先走找大，left再走找小，找到交换

继续找大找小

相遇停下来，和key交换

1.2为什么相遇位置一定比key小

这里我们有一个问题：为什么相遇位置一定比key小？

因为右边先走

相遇有两种情况：

1. right遇left -> left先走，right没有遇到比key小的，一直走，直到遇到left停下来，left存的是比key小的值
2. left遇right?-> right先走，left没有遇到比key大的，一直走，直到遇到right停下来，right存的是比key大的值
3. 所以我们得出一个结论，左边做key，右边先走；右边做key，左边先走

如果左边有序，右边也有序，整体就有序了

那么如何让左右有序呢？

类似二叉树，递归左树和右树

第一遍排序后的left和right的范围是：[begin,keyi-1]，keyi，[keyi+1,end]

然后继续递归，直到这个区间只有一个值或者不存在

1.3代码示例

//hoare方法
int PartSort1(int*a,int begin,int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int left = begin, right = end;
	int keyi = begin;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;
	return keyi;
}

2.挖坑法?

https://img-blog.csdnimg.cn/c2dde0e21f32461fb43db524559ca36d.gif#pic_center

2.1图示

right找小，left找大，right先走，找到小和坑位交换，然后left走，left找到大之后和坑位交换，交替进行直到相遇

他们一定会相遇到坑的位置

相遇之后将key的值放到坑位中，这时候key左边就是比key小的，key右边就是比key大的

2.2代码示例

我们写一个挖坑法的函数来排keyi左右的数据

先用三数取中方法得到keyi，定义一个key保存keyi的值，定义一个坑位holei先放到begin

• 右边找小，填到左边的坑里，右边成为新的坑
• 左边找大，填到右边的坑里，左边成为新的坑?
• 相遇后将key放到坑里，返回坑的下标?

//挖坑法
int PartSort2(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int key = a[begin];
	int holei = begin;
	while (begin < end)
	{
		//右边找小
		while (begin < end && a[end] <= key)
			--end;
		a[holei] = a[end];
		holei = end;
		//左边找大
		while (begin < end && a[begin] >= key)
			++begin;
		a[holei] = a[begin];
		holei = begin;
	}//相遇
	a[holei] = key;
	return holei;
}

3.前后指针法

https://img-blog.csdnimg.cn/8baec430614e47dfa382926553830c14.gif#pic_center

3.1图示

prev要不就是紧跟cur，要不prev和cur之间就是比key大的值

3.2代码示例

//前后指针法
int PartSort3(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int keyi = begin;
	int prev = begin, cur = begin + 1;
	while (cur <= end)
	{
		//if (a[cur] < a[keyi])
		//{
		//	++prev;
		//	Swap(&a[prev], &a[cur]);
		//	++cur;
		//}
		//else
		//	++cur;
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);
		++cur;
	}
	Swap(&a[keyi], &a[prev]);
	keyi = prev;
	return keyi;
}

4.快速排序优化

1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序

4.1三数取中方法

这里我们的key默认取的是第一个数，但是这种情况有个弊端，不能保证key一定是那个中间值，可能是最小的，也可能是最大的

但是理想情况下，key选中间值是效率最高的，每次都是二分?

这里就有一个方法能很好的解决这个问题：三数取中

我们写一个取中函数，将中间值与begin交换，还是将key给到begin

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

三数取中可以排除掉最坏的情况，相对而言可以提高效率

4.2小区间优化

如果是满二叉树，最后一层占50%的节点，倒数第二层占25%，倒数第三层占12.5%

假设我们要对这五个数排序，就需要调用六次递归，这代价是非常大的

我们可以使用插入排序，插入排序对局部的适应性是很好的，所以我们在这个区间缩小的一定范围的时候就可以使用插入排序

一般选择最后三到四层，因为最后三层就占据了将就90%的递归，将最后三层的递归消除是能够明显提高效率的

剩下的区间不一定是从0开始的，也有可能是后半段，所以这里插入排序从begin开始

总代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}
}
int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	if (a[begin] < a[midi])
	{
		if (a[midi] < a[end])
			return midi;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else
	{
		if (a[midi] > a[end])
			return midi;
		else if (a[end] > a[begin])
			return begin;
		else
			return end;
	}
}
//hoare方法
int PartSort1(int*a,int begin,int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int left = begin, right = end;
	int keyi = begin;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;
	return keyi;
}
//挖坑法
int PartSort2(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int key = a[begin];
	int holei = begin;
	while (begin < end)
	{
		//右边找小
		while (begin < end && a[end] <= key)
			--end;
		a[holei] = a[end];
		holei = end;
		//左边找大
		while (begin < end && a[begin] >= key)
			++begin;
		a[holei] = a[begin];
		holei = begin;
	}//相遇
	a[holei] = key;
	return holei;
}
//前后指针法
int PartSort3(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
	int keyi = begin;
	int prev = begin, cur = begin + 1;
	while (cur <= end)
	{
		//if (a[cur] < a[keyi])
		//{
		//	++prev;
		//	Swap(&a[prev], &a[cur]);
		//	++cur;
		//}
		//else
		//	++cur;
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);
		++cur;
	}
	Swap(&a[keyi], &a[prev]);
	keyi = prev;
	return keyi;
}
//快排
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	if (end - begin + 1 <= 10)
		InsertSort(a + begin, end - begin + 1);
	else
	{
		//hoare法
		//int keyi = PratSort1(a, begin, end);
		//int keyi = PartSort2(a, begin, end);
		int keyi = PartSort3(a, begin, end);
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}
int main()
{
	int a[] = { 9,8,7,6,6,5,4,3,2,1,10,14,12,11,15 };
	int n = sizeof(a) / sizeof(a[0]);
	QuickSort(a, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}