【算法导论】之快速排序

发表于2021-06-29更新于2021-06-29字数统计1.8k阅读时长22分阅读次数

大家好，我是希达。

前言

最近学习了算法导论上的快速排序部分，有不少体会。

今天就来分享一下。在此欢迎大家批评指正文中的错误。

快速排序

正文

1.快速排序的优点

说起快速排序，它的名字就显现出快排最大的优点————快。到底有多快呢？咱们用数据说话:
RaYxOS.png

综合一般情况来说，快排确实有(亿点快)。特别是对较大数据量的排序。

快速排序的综合时间复杂度是O(nlgn),但在极端最坏情况下，时间复杂度会到O(n^2)。

很多人在看到O(n^2)会产生疑问？为什么我们还要在实际生活中使用快排呢。

尽管快排的最坏时间复杂度很差，但是它的平均性能好，通常是实际排序中最好的选择。它的期望时间复杂度是O(nlgn)，(绝大多数是这样，在下文快排的性能分析中会有说明)，在排序中很少遇到最坏情况。并且O(nlgn)中隐含的常数因子非常小。
在C++库函数中sort()函数底层大部分用快排实现的(可以参照下文的小区间优化)。

所以：快排，yyds！！！

2.快排的原理及实现

我们来理解快排的原理。快排运用了分治的思想。

RawLWj.png

在每一次排序中，选取一个数据作为主元x，在将数据的每个值与主元x进行比较，使每趟排序结束时，小于或等于x的在x数据的左边，大于或等于x的在x的右边。(和x相等的数可以在x的两侧，这就造成了快排的不稳定性)。

左子区间都是不大于x的数，右子区间都是不小于x的数。以x为界限，递归左右子区间。从大致有序到全部有序。

下面我们来简单实现快速排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void quick_sort(int *a, int l, int r)
{
	if (l >= r)
		return;
	int x = a[l];    // 取最左边的值作为主元x
	int i = l, j = r;
	while (i < j)
	{
		while (a[i] <= x && i<r) ++i;    // 循环结束时a[i]比x大
		while (a[j] >= x && j>l) --j;    // 循环结束时a[j]比x小
		if (i < j)
			swap(a[i], a[j]);       // 交换a[i],a[j]
	}
	// j为分界点
	swap(a[l], a[j]);     // 将主元x放在正确的位置，作为分界点

	// 递归左右子区间
	quick_sort(a, l, j - 1);
	quick_sort(a, j+1, r);
}

3.快排的性能分析

我们对上面的代码进行分析：

  1. 最理想的情况：每次循环的主元x都在区间的中间，遍历一次数据的复杂度为O(n)，递归次数为lgn，所以时间复杂度为O(nlgn)。

  2. 最坏的情况：当输入的数据基本有序(逆序)时，在递归时，产生两个大小为n-1和0的子区间，使递归的深度为n，时间复杂度变为O(n^2)。效率不及插入排序（后面会介绍用插入排序实现小区间优化以减少递归的栈深度）

  3. 就平均情况来看。左区间长度：右区间长度=n。当n为9:1或者99:1时，只要n为常数比例的，算法的时间复杂度总是O(nlgn)。

快排的几种优化方式

对于快速排序，我们有很多优化方式避免快排达到最坏时间复杂度。

1.主元的随机化选取

我们将主元的选取随机化，可以降低快排达到最坏时间复杂度的可能性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void quick_sort(int *a, int l, int r)
{
	if (l >= r)
		return;
	int k = rand() % (r - l + 1) + l;  // 产生l到r的随机数
	 // 从a[l]到a[r]中随机选取
	swap(a[l], a[k]);
	int x = a[l];
	int i = l, j = r;
	while (i < j)
	{
		while (a[i] <= x && i<r) ++i;    // 循环结束时a[i]比x大
		while (a[j] >= x && j>l) --j;    // 循环结束时a[j]比x小
		if (i < j)
			swap(a[i], a[j]);       // 交换a[i],a[j]
	}
	// j为分界点
	swap(a[l], a[j]);     // 将主元x放在正确的位置，作为分界点

	// 递归左右子区间
	quick_sort(a, l, j - 1);
	quick_sort(a, j + 1, r);
}

2.三数取中

三数取中比主元的随机化更有优势。
三数取中的意思是：在a[l],a[(l+r)/2],a[r]三个数中选取中间大的数作为主元，可以有效的优化快排效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int Getmid(int *a, int l, int r)
{
	// 取得中间值的下标
}

void quick_sort(int *a, int l, int r)
{
	if (l >= r)
		return;
	swap(a[l], a[Getmid(a, l, r)]);       // 三数取中
	int x = a[l];
	int i = l, j = r;
	while (i < j)
	{
		while (a[i] <= x && i<r) ++i;    // 循环结束时a[i]比x大
		while (a[j] >= x && j>l) --j;    // 循环结束时a[j]比x小
		if (i < j)
			swap(a[i], a[j]);       // 交换a[i],a[j]
	}
	// j为分界点
	swap(a[l], a[j]);     // 将主元x放在正确的位置，作为分界点

	// 递归左右子区间
	quick_sort(a, l, j - 1);
	quick_sort(a, j + 1, r);
}

3.减小递归的栈深度——小区间优化

在C++库函数中sort()的底层实现是有一部分是快排的小区间优化。

我们看一下sort()函数底层实现的源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void
    __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
	   _Compare __comp)
    {
      if (__first != __last)
	{
	// sort函数默认为内省排序，当子数组小于16时返回
	  std::__introsort_loop(__first, __last,
				std::__lg(__last - __first) * 2,
				__comp);
	// 对大致排序过的数组进行插入排序操作
	  std::__final_insertion_sort(__first, __last, __comp);
	}
    }

小区间优化：在子区间的长度小于16时，进行插入排序，减小递归的栈深度。
模拟实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void Insert_sort(int *a, int l, int r)
{
	for (int i = l + 1; i < r; ++i)
	{
		if (a[i] < a[i - 1])
		{
			int j = i, k = a[i];
			while (a[i]<a[--j] && j>l);
			int tmp = j;
			while (j < i)
			{
				a[j + 1] = a[j];
				++j;
			}
			a[tmp] = k;
		}
	}
}
void quick_sort(int *a, int l, int r)
{
	if (r - l < 16)           // 在子区间的长度小于16时，进行插入排序，减小递归的栈深度
		Insert_sort(a, l, r);
	int x = a[l];    // 取最左边的值作为主元x
	int i = l, j = r;
	while (i < j)
	{
		while (a[i] <= x && i<r) ++i;    // 循环结束时a[i]比x大
		while (a[j] >= x && j>l) --j;    // 循环结束时a[j]比x小
		if (i < j)
			swap(a[i], a[j]);       // 交换a[i],a[j]
	}
	// j为分界点
	swap(a[l], a[j]);     // 将主元x放在正确的位置，作为分界点

	// 递归左右子区间
	quick_sort(a, l, j - 1);
	quick_sort(a, j+1, r);
}

4.其他优化：

算法导论还提到了其他的优化方法，比如用尾递归减少栈深度，针对相同元素值的快速排序等等。

欢迎大家在下方留言。