自动搬运

查看原文

来自洛谷，原作者为

	Allen_123 believe my lie

搬运于2025-08-24 21:22:06，当前版本为作者最后更新于2023-05-03 15:24:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本题解/笔记专门讲述快速排序及其应用，比较适合新手学习和阅读，如果想了解其他做法请移步。

对于一些评论的回复：虽然 C++ 确实提供了 sort 这个可以大幅简化代码的函数，但是如果想要理解排序方式的内部逻辑，请不要在模板题上耍小聪明（除非想要练习 sort）。其他题 sort 想怎么用就怎么用。

2023.12.15：修改了一些笔误和可能引起误解的内容。

2024.8.16：优化了一些表述，使描述更加严谨。

2024.11.26：修改了一些 typo 和小错误，增加后记。

2025.8.10：修改关于时间复杂度的表述，修改后记。

---

快速排序是 OI 中常用的算法。这篇题解/笔记将会详细地讲解快速排序的原理、实现过程，也会拓展 STL sort 函数的使用和快排复杂度及其证明。

快速排序的原理

本部分讲述的是常用的三路快速排序。如果想了解快速排序的更多变种实现方式可以在 OI Wiki 中了解。

我们设待排序的序列为一个长度为 $n$ 的序列 $a$。快速排序的具体原理如下：

首先，在 $a$ 中随机选择一个数 $x$，之后我们进行如下操作：

1. 如果 $n=0$ 或 $n=1$，此时根本无需排序，直接退出；
2. 定义三个新的序列 $b, c, d$；
3. 遍历整个序列 $a$，将比 $x$ 小的放在 $b$ 内，比 $x$ 大的放在 $d$ 内，和 $x$ 相等的放在 $c$ 内；
4. 将 $b, d$ 按如上过程继续排序。序列 $c$ 中的数由于都相等所以不必排序。

例如，我们定义一个未排序序列 $a=\{3, 2, 4, 1\}$。

我们从序列中选择第一个数 $a_1=3$，根据上面的过程可知，$b=\{2, 1\}, c=\{3\}, d=\{4\}$。

此时因为 $c, d$ 长度已经为 $1$，所以不必再排序；而同理，在序列 $b$ 中，我们可以将两个数分为两个序列（相当于把它们交换位置），最终就可以完成排序。排序结果为 $a=\{1, 2, 3, 4\}$。

---

快速排序如何用 C++ 实现？

我们以 P1177 【模板】排序为例来讲解这一算法的实现过程。

普通自定义函数

首先，我们看完如上所示的实现方法与过程后，可以发现：实际上每一次的排序之后都会通过调用本身来继续排序，这明显就是递归的精髓。

确实，递归是快速排序的主要思想，通过递归，我们将一个完整的序列经过不断的分解来变成很多个小序列，直到只有一个或没有数为止。这种排序就是在不断的递归和分解当中来慢慢实现与完成排序。

这里，我们提供了这个函数的参考代码：

// 注：四个数组的下标均从 0 开始。
// 请在主函数内设置随机种子，例如 srand(time(0))，否则可能会超时。
int randint(int l, int r){ // 生成在 [l, r] 之间的随机数
	return rand() % (r - l + 1) + l;
}
void qsort(int l, int r){ // l 为左端点，r 为右端点
	if(l >= r){ // 如果长度为 0 或 1 就返回
		return;
	}
	int num = randint(l, r), ind1 = 0, ind2 = 0, ind3 = 0; // 随机选择一个数，并定义三个作为下标的变量来记录长度、存放数据
	for(int i = l;i <= r;i++){ // 将 a 中的数分别分到 b, c, d（如上所述）
		if(a[i] < a[num]){
			b[ind1++] = a[i];
		}
		else if(a[i] == a[num]){
			c[ind2++] = a[i];
		}
		else{
			d[ind3++] = a[i];
		}
	}
	for(int i = 0;i < ind1;i++){ // 将 b, c, d 中的数重新放回 a
		a[i + l] = b[i];
	}
	for(int i = 0;i < ind2;i++){
		a[i + ind1 + l] = c[i];
	}
	for(int i = 0;i < ind3;i++){
		a[i + ind1 + ind2 + l] = d[i];
	}
	qsort(l, l + ind1 - 1); // 继续递归，排序原来的 b 和 d
	qsort(l + ind1 + ind2, r);
}

拓展：STL sort 函数的使用

（自定义比较方式时，除了下文所述的比较函数仍然有其他方法，感兴趣的读者可以自行了解，此处不再赘述。）

除了如上的快排模板外，我们还可以使用 C++ algorithm 头文件中的 sort 函数来直接完成排序。其使用方法如下：

我们设我们排序的数组为 $a$，排序区间为 $[l, r)$（即所有满足 $l\le x<r$ 的整数 $x$），且从小到大排序。则调用方法为：sort(a + l, a + r)。对于本题，就可以通过 sort(a + 1, a + n + 1) 自动完成排序。

注意，如果要使用这个函数，应该在头文件中加上 #include <algorithm> 或者 #include <bits/stdc++.h>（万能头文件）。

如果我们不想从小到大排序，而是想从大到小排序，或者以其他方式进行排序，那么我们就应该写一个比较函数（一般命名为 cmp）来改变排序方法。

例如我们想要把一个类型为 int 的数组从大到小排序，我们应该这么定义这个比较函数：

bool cmp(int a, int b){
	return a > b;
}

我们只需要定义两个与数组类型相同的变量作为参数，再返回两个数字的比较就可以了。

如果是从小到大排序，就用小于号连接两数；如果是从大到小排序，就用大于号连接两数。注意比较函数中的大于号、小于号不应改为大于等于号、小于等于号，否则会出现栈溢出等问题，导致意外的结果（例如运行时错误）。

写完这个函数，我们只需要在调用 sort 函数时在第三个参数写上函数名（例如 sort(a + l, a + r, cmp);）就可以了。值得一提的是，简单的比较函数（例如 less<int>()、greater<int>()）在 C++ 中是自带的，如果要从大到小排序，就可以直接将第三个参数替换为 greater<int>()。

同样，结构体也可以用它排序。

例如我们定义一个结构体：

struct node{
	int x, y;
}c[1005];

此时，我们想这样对 $c$ 的第 $1$ 到 $1000$ 项按如下所示的方式排序：$x$ 更大的在前，如果 $x$ 相同则 $y$ 更大的在前，那么我们可以这样写比较函数：

bool cmp(node a, node b){
	if(a.x != b.x){ // 如果两个 x 不等则以 x 的大小排序
		return a.x > b.x;
	}
	return a.y > b.y; // 否则以 y 的大小排序
}
sort(c + 1, c + 1001, cmp);

在排序时，可以通过以上所述的比较函数、重载运算符或者其他方式进行自定义比较，但是在比较方式不明确的情况下就无法排序，导致编译失败。故在排序时需要确认比较方式明确。

---

快速排序的复杂度

时间复杂度$^{[1]}$

快速排序最好情况下的时间复杂度为 $\operatorname O(n\log n)$，一般情况下的复杂度为 $\operatorname O(n\log n)$，优化（取中位数）情况下最坏时间复杂度为 $\operatorname O(n\log n)$，随机化情况下最坏时间复杂度为 $\operatorname O(n^2)$。如下是其证明：

根据快速排序的实现过程和如上代码可以发现，每一次将原序列分为 $3$ 个序列的过程的时间复杂度是 $\operatorname O(n)$。

对于最优情况，当每一次随机选择的都是序列的中位数时，我们要排序的序列将被分成两个长度相差不多的两个序列。此时时间复杂度的递推式满足 $T(n)=2T(\frac{n}{2})+\operatorname O(n)=\operatorname O(n\log n)$，所以其最好情况为 $\operatorname O(n\log n)$；

对于最坏情况，当每一次选择的都是数列的最值（一个典型的例子就是数列已经有序），此时除了与选定的数相等的数以外，剩下的数仍然需要排序（一个序列为空，另一个包含了除与选定的数相等的数以外的所有数），此时的复杂度递推式为 $T(n)=T(n-1)+n=\operatorname O(n^2)$，所以快速排序的最坏时间复杂度为 $\operatorname O(n^2)$。由于我们每次会随机选择，所以一般情况下带随机化的快速排序复杂度不会达到 $\operatorname O(n^2)$。

如果想要让快速排序较为稳定，在快速排序的过程中，我们可以遍历一遍待排序数组，并找出其中位数，这样会使得剩余待排序数组大小尽可能接近 $\frac{n}{2}$，保证了 $\operatorname O(n\log n)$ 的时间复杂度。无论是否加入中位数优化，在日常训练和比赛中，我们一般都认为快排的时间复杂度为 $\operatorname O(n\log n)$。

篇幅所限，这里无法提供一般情况下快排复杂度的证明，感兴趣的读者可以参考《算法导论》第 $7$ 章第 $4$ 节或查看 OI Wiki 中的相关内容。

空间复杂度

由于快速排序只需要一个序列来储存序列中的数（也可以再多加几个作为辅助），所以其空间复杂度为 $\operatorname O(n)$。如果进行了一些优化可以降低额外的空间复杂度，但不影响总体的空间复杂度。

---

尾声

排序虽是最基本的普及组算法，但在信息学竞赛中往往有着无比重要的辅助作用，也是在思考题目时的重要思维支柱。未来的路还有很长，无论结局如何，愿大家在 OI 中付出的每一份努力都无愧最初的决定。

祝大家 OI 旅途好运。

---

引用

$[1]$：部分引用 OI Wiki 中有关快速排序-时间复杂度的内容。