【数据结构】排序算法---快速排序

1. 定义

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要$O(nlogn)$次比较。在最坏状况下则需要$O(n^2)$次比较，但这种状况并不常见。事实上，快速排序通常明显比其他$O(nlogn)$算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然最坏的情况下的时间复杂度达到了$O(n^2)$，但是人家就是优秀，在大多数情况下都比平均时间复杂度为$O(nlogn)$的排序算法表现要更好，可是这是为什么呢? 在《算法艺术与信息学竞赛》上有给出满意的答案：

快速排序的最坏运行情况是$O(n^2)$，比如说顺序数列的快排。但它的平摊期望时间是$O(nlogn)$，且$O(nlogn)$记号中隐含的常数因子很小，比复杂度稳定等于 $O(nlogn)$的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

2. 算法步骤

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下（以升序为例）：

1. 从数列中挑出一个元素，称为 “基准”（pivot）；

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

3. 动图演示

4. 性质

稳定性：

快速排序是一种不稳定的排序算法。

空间复杂度：

冒泡排序的空间复杂度为$O(logn)$

时间复杂度：

快速排序的最优时间复杂度和平均时间复杂度为$O(nlogn)$，最坏时间复杂度为 $O(n^2)$。

• 对于最优情况，每一次选择的分界值都是序列的中位数，此时算法时间复杂度满足的递推式为$T(n)=2T(\frac{n}{2})+O(n)$，由主定理，$T(n)=O(nlogn)$。

• 对于最坏情况，每一次选择的分界值都是序列的最值，此时算法时间复杂度满足的递推式为$T(n)=T(n-1)+O(n)$，累加可得$T(n)=O(n^2)$。

• 对于平均情况，每一次选择的分界值可以看作是等概率随机的。

在实践中，几乎不可能达到最坏情况，而快速排序的内存访问遵循局部性原理，所以多数情况下快速排序的表现大幅优于堆排序等其他复杂度为$O(nlogn)$的排序算法。

5. 递归版本代码实现

快速排序实现主框架：

//快速排序
void QuickSort(int* a, int left, int right)
{
	if (left >= right) {
		return;
	}
	//_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分
	int meet = _QuickSort(a, left, right);
	QuickSort(a, left, meet - 1);
	QuickSort(a, meet + 1, right);
}

将区间中的元素进行划分的_QuickSort方法主要有以下几种实现方式：

5.1 hoare版本

算法思路：

（1）创建左右指针，确定基准值

（2）从右向左找出比基准值小的数据，从左向右找出基准值大的数据，左右指针数据交换，进入下次循环

问题1：为什么跳出循环后right位置的值一定不大于key？

当left > right时，即right走到left的左侧，而left扫描过的数据均不大于key，因此right此时指向的数据一定不大于key

问题2：为什么left 和 right指定的数据和key值相等时也要交换？

相等的值参与交换确实有一些额外消耗。实际还有各种复杂的场景，假设数组中的数据大量重复时，无法进行有效的分割排序。

代码：

int _QuickSort(int* a, int left, int right)
{
	int begin = left;
	int end = right;
	int keyi = left;
	++left;
	while (left <= right)
	{
		// 右边找小
		while (left <= right && a[right] > a[keyi])
		{
			--right;
		}
		// 右边找小
		while (left <= right && a[left] < a[keyi])
		{
			++left;
		}
		if (left <= right)
		{
			swap(&a[left++], &a[right--]);
		}
	}
	swap(&a[keyi], &a[right]);
	return right;
}

5.2 挖坑法

算法思路：

创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放入当前的"坑"中，返回当前"坑"下标（即分界值下标）

代码：

int _QuickSort(int* a, int left, int right)
{
	int mid = a[left];
	int hole = left;
	int key = a[hole];
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

5.3 lomuto前后指针

算法思路：创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。

代码：

int _QuickSort(int* a, int left, int right)
{
	int prev = left, cur = left + 1;
	int key = left;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)
		{
			swap(&a[cur], &a[prev]);
		}
		++cur;
	}
	swap(&a[key], &a[prev]);
	return prev;
}

6. 优化

朴素优化思想

较为常见的优化思路有以下三种：

• 通过 三数取中（即选取第一个、最后一个以及中间的元素中的中位数） 的方法来选择两个子序列的分界元素（即比较基准）。这样可以避免极端数据（如升序序列或降序序列）带来的退化；
• 当序列较短时，使用 插入排序 的效率更高；
• 每趟排序后，将与分界元素相等的元素聚集在分界元素周围，这样可以避免极端数据（如序列中大部分元素都相等）带来的退化。

下面介绍几种较为成熟的快速排序优化方式：

• 三路快速:三路快速排序（英语：3-way Radix Quicksort）是快速排序和 [基数排序] 的混合。它的算法思想基于 [荷兰国旗问题]的解法。
• 内省排序（英语：Introsort 或 Introspective sort）是快速排序和 [堆排序]的结合，由 David Musser 于 1997 年发明。内省排序其实是对快速排序的一种优化，保证了最差时间复杂度为$O(nlogn)$。

具体相关介绍看文章：https://oi-wiki.org/basic/quick-sort/

7. 非递归版本代码实现

非递归版本的快速排序需要借助数据结构：栈

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);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);
		// 单趟
		int keyi = begin;
		int prev = begin;
		int cur = begin + 1;
		while (cur <= end)
		{
			if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[prev], &a[cur]);
			++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);
}

结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。

也可以点点关注，避免以后找不到我哦！

Crossoads主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的动力！

带你初步了解排序算法：https://blog.csdn.net/2301_80191662/article/details/142211265
直接插入排序：https://blog.csdn.net/2301_80191662/article/details/142300973
希尔排序：https://blog.csdn.net/2301_80191662/article/details/142302553
直接选择排序：https://blog.csdn.net/2301_80191662/article/details/142312028
堆排序：https://blog.csdn.net/2301_80191662/article/details/142312338
冒泡排序：https://blog.csdn.net/2301_80191662/article/details/142324131
快速排序：https://blog.csdn.net/2301_80191662/article/details/142324307
归并排序：https://blog.csdn.net/2301_80191662/article/details/142350640
计数排序：https://blog.csdn.net/2301_80191662/article/details/142350741
桶排序：https://blog.csdn.net/2301_80191662/article/details/142375338
基数排序：https://blog.csdn.net/2301_80191662/article/details/142375592
十大经典排序算法总结与分析：https://blog.csdn.net/2301_80191662/article/details/142211564