【初阶数据结构】排序——交换排序-快速排序

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

Hoare版

基本思想：
1.任取待排序元素序列中的的某元素作为基准值，并定义两个指针分别指向序列的开始和结尾，遍历该数据，根据规则进行交换以及指针的移动，直至两指针相遇。
2.此时将基准值与两指针相遇指向的值交换，此时基准值就到了正确的位置。
3.此时将该序列分成了左右两边，左边序列的数都比此基准值小，右边序列的数都比此基准值大。
4.再重复上述步骤，可将所有数排好。

其实也就是递归。

当说可能不太清楚，下面我们通过图来解释：
在这里插入图片描述

总体代码如下：

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

void QuickSort1(int* a, int left, int right)
{
	if (left >= right)//递归结束条件，如果区间中只有一个值或不存在
		return;
	int begin = left, end = right;
	int key = left;//用的都是下标
	while (left < right)
	{
		while (left < right && a[right] >= a[key])//让右指针先走，右指针要找到比a[key]小的
			right--;
		while (left < right && a[left] <= a[key])//左指针后走
			left++;
		Swap(&a[left], &a[right]);
	}
	//此时left和right相遇
	Swap(&a[left], &a[key]);
	//更新key的下标
	key = left;
	//分了左右两个区间[begin, key-1] key [key+1, end]
	//递归，使剩余区间都按上面操作
	QuickSort1(a, begin, key - 1);
	QuickSort1(a, key + 1, end);
}

拓展：我们最后是让left和right相遇所指向的值与基准值交换，我们是要升序排序，这也就是二者相遇指向的值必定小于基准值，这是为什么呢？
原因如下：

很重要的一点就是右边先走保证的，二者相遇无非就两种情况，一种是left遇上right，另一种就是right遇上left。下面来分别讨论：
left遇上right：right先走，当right走到比key小的值就停了下来，left再走，要找比key大的值，但是它找不到，一直走就会和right想遇，此时相遇所指向的值就比key小。
right遇上left：如果第一轮二者就相遇：right先走，right没有找到比key小的值，就一路左移，遇到left，也就是key的位置。
right遇上left：二者第一轮以后相遇，此时二者是经过第一轮的交换，也就是left此时指向的位置比key小，right先走，它没有找到比key小的值，一直左移就和left相遇，此时指向的还是比key小的值。

因此，只要保证让right先走，在升序时就能保证相遇时所指向的值小于基准值。

前后指针版

给定两个指针，一个prev指向key位置处，另一个cur指向prev的下一个位置。
基本思想：

a[cur] >= a[key]，++cur；
a[cur] < a[key]，++prev，交换prev和cur位置的值，++cur；

在这里插入图片描述
通过上述步骤可以发现，prev和cur之间的数都是比基准值大的，也就是通过不断交换，将比基准值大的数都被放在了prev和cur之间，则当cur走到最后时，二者之间就都是比cur大的了。
后面的同样根据上述步骤重复进行即可得到。
具体代码如下：

void QuickSort2(int* a, int left, int right)
{
	if (left >= right)//递归结束条件，如果区间中只有一个值或不存在
		return;
	int prev = left, cur = left + 1;
	int key = left;
	while (cur <= right)
	{
		if (a[cur] < a[key])
		{
			++prev;
			Swap(&a[prev], &a[cur]);
			cur++;
		}
		else
			cur++;
	}
	Swap(&a[key], &a[prev]);
	key = prev;
	//分了左右两个区间[begin, key-1] key [key+1, end]
	//递归，使剩余区间都按上面操作
	QuickSort2(a, left, key - 1);
	QuickSort2(a, key + 1, right);
}

优化

由于快排是一种递归式的排序，时间复杂度和堆排差不多，都是O(NlogN)。但如果序列有序或者接近有序时，此时时间复杂度就会高很多，就几乎达到了O(N^2^)。这是取基准值一直取的第一个导致的。

在这里插入图片描述
因此解决办法就是在每次对基准值的查找不要一直是第一个。下面有几种方式：

三数取中法

基本思想：
在需要排序的序列中，找到最左边，最右边以及中间的三个数，将这三个数比较大小，取中间大的数字。并将此数字作为基准值，然后将其与最左边的数交换，使基准值保持在最左边的位置，便于后续遍历。

适用序列：有序或接近有序的情况。
核心：找到中间大的数。
在这里插入图片描述
具体代码如下：

int GetMid(int* a, int left, int right)//三数取中
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left] < a[right])//a[mid]>=a[right]
			return right;
		else
			return left;
	}
	else//a[left]>=a[mid]
	{
		if (a[right] < a[mid])
			return mid;
		else if (a[left] < a[right])//a[mid]<=a[right]
			return left;
		else
			return right;
	}
}
void QuickSort1(int* a, int left, int right)
{
	if (left >= right)//递归结束条件，如果区间中只有一个值或不存在
		return;
	int begin = left, end = right;
	//找到中间的数
	int mid = GetMid(a, left, right);
	//与最左边的值交换
	Swap(&a[mid], &a[left]);
	int key = left;//用的都是下标
	//......
}

取随机数做基准值

我们不想每次都取最左边的值做基准值，那我们在[left, right]此区间内找随机值即可。思想还是比较简单的。
具体代码如下：

void QuickSort1(int* a, int left, int right)
{
	if (left >= right)//递归结束条件，如果区间中只有一个值或不存在
		return;
	int begin = left, end = right;
	//要使得所取的随机数在[left, right]区间中
	int randi = rand() % (right - left +1);
	//left不一定为0
	randi += left;
	//与最左边的值交换
	Swap(&a[randi], &a[left]);
	int key = left;//用的都是下标
	//......
}

小区间优化

正如堆所示，最后两到三层的节点数量占了整个的百分之八十左右，此时我们用递归消耗是比较大的，因此我们可以在最后的区间内使用插入排序。减少消耗。
代码如下：

void QuickSort1(int* a, int left, int right)
{
	if (left >= right)//递归结束条件，如果区间中只有一个值或不存在
		return;
	int begin = left, end = right;
	//小区间优化
	if (right - left + 1 < 10)
	{
		InsertSort(a + left, right - left + 1);
	}
	else
	{
		//要使得所取的随机数在[left, right]区间中
		int randi = rand() % (right - left + 1);
		//left不一定为0
		randi += left;
		//与最左边的值交换
		Swap(&a[randi], &a[left]);
		/*int mid = GetMid(a, left, right);
		Swap(&a[mid], &a[left]);*/
		int key = left;//用的都是下标
		//.........
		QuickSort1(a, begin, key - 1);
		QuickSort1(a, key + 1, end);
	}
	
}

快排特性总结：

时间复杂度：O(NlogN)，每趟确定的元素呈现指数增长。
空间复杂度：O(logN)，递归是需要用的栈空间
稳定性：不稳定

快排非递归版

将递归转化为非递归，可以借助循环来解决。
我们可以借助栈后进先出的思想来模拟递归区间的使用。
如图：
在这里插入图片描述
判断是否入栈：看区间是否有两个以上的值，如果只有一个值就没有必要入栈排序了。
判断while循环结束的条件：栈不为空则继续，为空则结束。
代码如下：

#include"Stack.h"
void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);//初始化栈
	STPush(&st, right);//先进右
	STPush(&st, left);//再进左

	while (!STEmpty(&st))//循环条件是栈不为空
	{
		int begin = STTop(&st);//左是后进的，所以取出来就是begin
		STPop(&st);

		int end = STTop(&st);
		STPop(&st);

		// 单趟
		int keyi = begin;
		int prev = begin;
		int cur = begin + 1;

		while (cur <= right)
		{
			if (a[cur] < a[key])
			{
				++prev;
				Swap(&a[prev], &a[cur]);
				cur++;
			}
			else
				cur++;
		}
		Swap(&a[keyi], &a[prev]);
		keyi = prev;
		// [begin, keyi-1] keyi [keyi+1, end] 
		if (keyi + 1 < end)//如果区间有两个值以上则入区间
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}
		if (begin < keyi-1)
		{
			STPush(&st, keyi-1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);//要记得把栈销毁
}

感谢大家观看，如果大家喜欢，希望大家一键三连支持一下，如有表述不正确，也欢迎大家批评指正。
请添加图片描述

秒客网