排序
排序（Round 1）
-1 检查浏览器渲染数学公式情况
因为笔者发布文章当天，本博客仍然存在 Latex 可能无法渲染的情况，下面是一个 Latex 示范：
$x$
- 如果正常显示为衡水体 x，则代表读者的浏览器已经成功渲染了 Latex
- 如果显示为 带有美元符号的 x 即
$x$（已除去换行符），则代表读者的浏览器没有成功渲染 Latex，读者可能需要刷新重试，如果刷新多次仍然无法渲染，请尝试换一个浏览器/网络环境
0 框架
在本文中，我将重点介绍 排序，感谢 深入浅出程序设计竞赛（基础篇） 提供重要支持，本文有一部分的内容是基于本书修改
排序 是在 OI 算法中重要的一部分，虽然大部分场景下都可以用 sort 解决（限于 bits/stdc++.h），但是掌握具体的内容还是必不可少的，相对于初赛而言
$$ \begin{aligned} &\textbf{排序（Round 1）} \begin{cases} &\text{计数排序}\\ &\text{选择排序、冒泡排序、插入排序}\\ &\text{快速排序}\\ &\text{排序算法的应用}\\ &\text{汇总}\\ \end{cases} \end{aligned} $$
1 计数排序
【题目样本 1.1】P1271【模板】排序
题目描述
https://www.luogu.com.cn/problem/P1271
学校正在选举学生会成员，有 $n(n \leq 999)$ 名候选人，每名候选人编号分别从 $1$ 到 $n$, 现在收集到了 $m(m \leq 200000)$ 张选票，每张选票都写了一个候选人编号
现在想把这些堆积如山的选票按照投票数字从小到大排序。输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字，求出排序后的选票编号。例如，当有 $5$ 个候选人，$10$ 张选票分别是 $2、5、2、2、5、2、2、2、1、2$ 时，需要输出 1222222255
分析
这题本质有很多方法，但是由于是 计数排序，因此：
在投票区放上 $n$ 个投票箱，投票人支持谁就把票投入对应的投票箱中，投票后只须统计每个投票箱有几张选票，直接按照候选人编号取出来就可以完成排序操作
也不需要排序了
参考代码
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,x,f[100005];
int main(){
cin>>n>>m;
for(i=1;i<=m;i++) cin>>x,f[x]++;
for(i=1;i<=n;i++) for(j=1;j<=f[i];j++) cout<<i<<" ";
}这里倡导数组从 $1$ 开始存
只需要开一个大小不小于 $n$ 的数组作为票箱，依次读入选票，然后将选票号数加到对应的票箱中，最后按照每个票箱的数量输出候选人编号即可
在这个过程中，甚至不需要存储下每一张选票
在完成输入并计算时，$f[]$ 状态如下
| $f$ | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 7 | 0 | 0 | 2 |
计数排序
这种排序方法被称为 计数排序
读入选票并统计的时间复杂度是 $O(m)$，输出选票的时间复杂度是 $O(m+n)$（第一层循环做 $n$ 次，$f[i]$ 至多为 $m$），空间复杂度是 $O(n)$（因为 $f[]$）
所以计数排序只能用于排序编号范围不是很大的数字，如果需要排序的数字要到 $10^9$，别说运行时间了，内存都无法存得下这么大的范围的数组
此外，如果希望将一些浮点数或者字符串进行排序，就没办法去建造合适的 投票箱，所以就不能使用这种算法了（把下标存成 $\text{浮点数} \times 10^\text{浮点数位数}$ 也是一个不错的选择）
也有改进方法，即 桶排序&基数排序，思路类似，但是复杂
无论是上段和计数，这些排序都是基于分类，并非比较
2 选择排序、冒泡排序、插入排序
【题目样本 2.1】数列排序
题目描述
输入 $n(n \leq 1000)$ 个数字 $a_i(a_i \leq 10^9)$, 将其从小到大排序后输出
分析
设有 $5$ 张纸牌，他们是 $4,1,9,5,1$，打牌时如何排序？
解法 1：选择排序
分析
求最大值：
max()求最小值：
min()求一序列最值：
for(int i=1;i<n;i++) ma=max(ma,a[i]);，a[]为序列，$n$ 为数量，$ma$ 存放最大值核心思想：打擂台
如何联想到本题？
[collapse status="false" title="答案"]
从第一张牌到最后一张牌中找到最小的一张，放在最前面的位置；然后从第二张牌到最后一张牌中继续找到最小的一张，放到第二位……如此反复，就可以得到从小到大的序列
[/collapse]
这里有一张不错的图，来自 深入浅出，因此贴在这
若遇到大小相等的牌，continue
参考代码片段
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++)
if (a[j] < a[i]) {
int p = a[i];
a[i] = a[j];
a[j] = p;
}
}解法 2：冒泡排序
分析
如果尝试把最大的一项放在后面，虽然可以倒过来使用选择排序，但是可以试试别的办法
这里有一张图，来自 豆包，它打了一个类似于文章的比方，讲述了 选择排序 与 冒泡排序 的区别，前情提要是 现有扑克牌：9、5，要排成5、9
首先比较第 $1$ 张牌和第 $2$ 张牌，如果后面的牌比前面的牌小，那么就交换位置；然后比较第 $2$ 张牌和第 $3$ 张牌，同样保证第 $3$ 张牌要大于第 $2$ 张牌……依此类推， 直到比较最后一张牌和倒数第二张牌，这样就能保证最后面的一张牌是最大的一张了
继续进行新的一轮，利用上面一样的交换，但是需要注意的是，由于最后一张牌已经是手牌中最大的一张了，所以只需要比较到倒数第二张就行了
这一轮后结束后倒数第二张牌就是第二大的牌（当然，也有可能是并列最大)。经过 $n-1$ 轮排序后，就得到了有序的手牌
下图同样来自 深入浅出，用于理解
参考代码片段
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++)
if (a[j] > a[j + 1]) {
int p = a[j];
a[j] = a[j + 1];
a[j + 1] = p;
}
}[scode type="green"]int p=a[j];a[j]=a[j+1];a[j+1]=p; 推荐用 swap(a[j],a[j+1]); 来取代，用于交换
[/scode]
解法 3：插入排序
分析
一种很形象的比喻
你在玩纸牌游戏的时候，从牌堆里面抽牌，抽到一张牌，放到你的手牌里，你是怎么保证手牌内的牌是有序的呢？
如果你能通过 Cloudflare 的人机验证，你应该会看看抓到牌的大小，再看看手牌，定位到合适的位置，插入
上面描述的过程，即 插入排序
- 把手牌分为有序的和无序的两部分
- 最开始有序的就只有一张牌，也就是第一张
- 要把接下来的 无序区 中的一张牌（称为 待插牌 ）插入到 有序区 中，就是从有序区的末尾开始往前比较，如果待插牌比正在比较的牌小，那么就把有序区的正在比较的牌往后面放一格，然后继续往前面进行比较，直到待插牌遇到不大于自己的牌或者成为第一个为止
- 这时，待插牌就可以填入留出来的缺口中。反复将无序区中的待插牌插入到有序区中，直到所有的牌都在有序区
同样的，这里有一张非常生动的图，供读者查阅
下面这是来自 深入浅出 的 插入排序 实现代码，进行了注释的补充
for(int i = 1; i < n; i++) {
int now = a[i], j; // 记录待插入元素，稍候会放进去
for(j = i - 1; j >= 0; j--) // 一个很经典的模板：元素后移
if(a[j] > now)
a[j + 1] = a[j]; // 大于now的元素后移
else
break;
a[j + 1] = now; // 插入到正确位置
}选择排序
为了加强读者的记忆，这里重新梳理一遍
解法 1 这种算法被称为 选择排序
从代码中可以看出有两重循环，读者可以自己计算一下已知 $n$ 的情况下一共需要比较的次数
选择排序的算法时间复杂度是 $O(n^2)$；由于只需要一个数组存下这些数字即可，空间复杂度是 $O(n)$
[collapse status="false" title="答案"]
$$ \frac{n(n-1)}{2} $$
[/collapse]
冒泡排序
解法 2 这种算法被称为 冒泡排序，在一轮中，最大的那张牌会一点一点地从左移动到右边，像冒泡泡一样
读者也可以计算一下排序的过程中需要进行几次比较
冒泡排序算法的时间复杂度也是 $O(n^2)$，空间复杂度也是 $O(n)$
冒泡排序相比于选择排序并没有实质性的改进
有一种冒泡排序的改良版叫作希尔排序，不是相邻位置的两个数字比较，而是比较距离更远的两个数字，虽然能略微优化一些复杂度，但依然不实用
猴子排序同样也是一种奇怪的办法
插入排序
这种算法叫作 插入排序
如果序列本来已经从小到大排序，那么每次无序区的待插牌都不会插进有序区中，而是紧贴在有序区后使有序区一直扩大，那么只需要 $n-1$ 次比较就可以完成算法流程
然而，如果序列是从大往小排序，那么每次插入都会将有序区中的所有牌往后面挪动一次，这样速度就非常慢了
讲时间复杂度一般会考虑最悲观的情况，所以插入排序的算法复杂度还是 $O(n^2)$，和选择排序、冒泡排序的复杂度一致，它们空间复杂度也是一样的
不过，如果能保证序列 基本有序 , 那么使用插入排序的效率可能会不错
不推荐在 Contest 中使用这些方法，耗时过久
笔者认为，学习这些是为了掌握原理，在第一轮比赛中获得较好的成绩，在历年的 OI 比赛中，有相当一部分的套题涉及了这个内容
3 快速排序
【题目样本 3.1】P1177 快速排序
题目描述
https://www.luogu.com.cn/problem/P1177
输入 $n(n \lt 10^5)$ 个数字 $a_i(a_i \lt 10^9)$，将其从小到大排序后输出
分析
这个数据量就很大了，插入排序、选择排序、冒泡排序都无法完成。这次将介绍在 OI 中最普遍使用的排序算法 快速排序，简称快排，顾名思义
快速排序说起来其实也挺简单的，但是需要读者能够理解递归
[collapse status="false" title="递归"]
递归就是函数调用自己。
你的快速排序就是递归：
void Qsort(int x, int y) {
if (x >= y) return; // 终止条件
// ... 分区操作 ...
Qsort(x, i); // 自己调用自己，排左边
Qsort(i+2, y); // 自己调用自己，排右边
}执行过程：先把数组分成左右两部分，然后分别对两部分再调用同样的函数继续分，直到每部分只剩一个元素。
每次调用会占用栈内存，递归太深会栈溢出。你的代码最坏情况（已有序数据）递归深度达 $200000$，风险很大。
上述内容来自 Deepseek V4 Pro，请注意辨别
[/collapse]
算法的大致过程是对于一个无序序列，找到一个 哨兵数 ，将序列中所有比哨兵数小的数字都在哨兵数的左边，所有比哨兵数大的数字都在哨兵数的右边；然后分别对哨兵数左边和右边再使用同样的方法找到新的哨兵数，并再次进行分类，直到集合不可分割为止
怎么选择哨兵呢？随便选，可以是第一个，可以是中间那个，也可以在序列中随机选择
选择好哨兵，然后从序列左端开始寻找第一个比哨兵大的数字，从右边选择第一个比哨兵小的数字，然后交换这两个数；接着继续从左边找到比哨兵大的数字，右边比哨兵小的数字并交换……直到将序列分为两组，左边序列都不大于哨兵，右边序列都不小于哨兵，就可以分别对左边和右边进行排序了
下面同样还有一张生动的图，建议配合代码食用
参考代码
有多种办法可以实现，这是一种实现办法，也基于书本内容进行了适当的补充更多的办法请前往 排序的应用 这一章节
void qsort(int a[], int l, int r) { // a[] 传递数组
int i = l, j = r, flag = a[(l + r) / 2], tmp; // flag是基准值（哨兵）
do {
while (a[i] < flag) i++; // 左指针右移，跳过比基准小的
while (a[j] > flag) j--; // 右指针左移，跳过比基准大的
if (i <= j) { // 找到一对需要交换的数
tmp = a[i]; a[i] = a[j]; a[j] = tmp;
i++; j--; // 继续移动指针
}
} while (i <= j); // 两指针未交错就继续
if (l < j) qsort(a, l, j); // 递归排左半部分
if (i < r) qsort(a, i, r); // 递归排右半部分
}快速排序
虽然在极端情况下（比如数列已经有序，且每次选择哨兵都会分出长度为 $1$ 的小段），快速排序的时间复杂度是 $O(n^2)$，但是如果随机选择哨兵，则很难出现这种情况
实际上，随机化快速排序的算法复杂度是 $O(n \log n)$，空间复杂度是 $O(n)$，而且不需要额外的辅助空间，所以是一种最为实用的排序算法
快速排序利用了 分治 思想，后面可能会出一篇 排序 这一专题的补充篇，介绍了更多的非基础排序
额外的，二分查找法 也利用了 分治思想，这个方法也可能会在未来单独出一篇专题进行讲解
【题目样本 3.2】 P1923 求第 $k$ 小的数
题目描述
https://www.luogu.com.cn/problem/P1923
输入 $n(n \lt 10^6 \text{ 且 } n \text{ 为奇数})$ 个数字 $a_i(a_i \lt 10^9)$，输出这些数字的第 $k$ 小的数，最小的数是第 $0$ 小
分析
如上 URL 中的 题目描述，如果你是真的要训练 快排，请 不要 使用 nth_element STL，当然我估计你也不知道
虽然可以直接排序，然后取数组中的第 $k$ 个作为答案进行输出，但是直接排序一遍的复杂度是 $O(n \log n)$，不适合这道头目，我们可以借鉴 快排 的 分治思想 把时间复杂度降至 $O(n)$
[collapse status="false" title="可以降低时间复杂度的原因"]
核心原因在于每次只需要递归处理一边，而不是两边
更多的：
快速排序的分治过程
每次选一个基准（pivot），将数组分成三部分：- 左边：所有元素 ≤ pivot
- 中间：pivot 本身
- 右边：所有元素 > pivot
然后递归地对左右两边分别排序，所以总复杂度是 (O(n \log n))。
求第 k 小数的优化
在快速选择（Quick Select）中，不需要对两边都排序，只需要判断第 k 小的数在哪一边：- 如果 (k) 小于左边元素个数，就只在左边递归查找
- 如果 (k) 等于左边元素个数 + 1，那么 pivot 就是答案
- 否则，只在右边递归查找，并且调整 k 的值
复杂度分析
- 每次递归处理的数组大小大约是上一次的一半（平均情况）
总比较次数：
$$ n + \frac{n}{2} + \frac{n}{4} + \cdots = 2n $$
- 因此平均时间复杂度是 (O(n))
上述内容来源 Deepseek V4 Pro 修改而得
[/collapse]
和快速排序的方法一样，任意取一个哨兵，将序列分为两部分，左边部分的所有数字都不大于右边的数字
- 如果 $k$ 在左边的范围，则递归求解左边的部分
- 如果在右边，则递归求解右边的部分
- 但是也有可能两边都不属于（比如说 $j=4$ 而 $i=6$ , 但刚好 $k=5$)，那么直接就可以给出答案
参考代码
这个代码是 深入浅出 提供的，由 Deepseek V4 Pro 和 笔者 改写而得
int ans = 0, k; // 记录答案，以及求第 k 小
void findkth(int a[], int l, int r) { // 引入数组的地址
if(l == r) {
ans = a[l]; // 区间长度为 1 时，记录答案
return;
}
int i = l, j = r, flag = a[(l + r) / 2], tmp;
do {
while (a[i] < flag) i++; // 从左找比哨兵大的数
while (a[j] > flag) j--; // 从右找比哨兵小的数
if (i <= j) { // 交换
tmp = a[i]; a[i] = a[j]; a[j] = tmp;
i++; j--;
}
} while (i <= j);
if (k <= j) findkth(a, l, j); // 第 k 小的数字在左区间
else if (i <= k) findkth(a, i, r); // 第 k 小的数字在右区间
else findkth(a, j + 1, i - 1); // 第 k 小的数字既不在左区间，也不在右区间
}尽管 此参考代码片段（快速选择） 相对于 快排（模板代码）类似，但是每次处理的区间长度期望下都会被减半，复杂度是线性的
快速排序 - 快速选择
这个概念是在书中没有的，是由 Deepseek V4 Pro 提出
它基于 快速排序 的分治思想，但并不是完整的排序算法，而是一种 选择算法 ——专门用来查找数组中第 $k$ 小（或第 $k$ 大）的元素
下面是一张表格，阐释了区别
| 快速排序 | 快速选择 | |
|---|---|---|
| 目的 | 将整个数组排好序 | 只找出第 $k$ 小的元素 |
| 递归方向 | 同时递归左右两边 | 只递归包含答案的那一边 |
| 时间复杂度 | (O(n \log n)) | 平均 (O(n)) |
| 是否完全排序 | 是 | 否 |
所以，这种方法叫做 快速选择，也可以理解为"快速排序的简化版"或"基于快排分治的选择算法"
[collapse status="false" title="函数图像（可能有误）"]
这个部分由 Deepseek V4 Pro 与 豆包 提供，它们分别为这个部分 提供函数生成代码 和 提供函数图，在这里表示对他们最诚挚的感谢
但是目前看起来它们携手合作画出来的图有误，作为初二学生的笔者，无法验证这张图的真伪，所以这个问题抛给读者，抱歉
[/collapse]
4 排序的应用
这里提供了一些 排序 的拓展用法，在第二轮比赛时可能有用
【题目样本 4.1】P1059 [NOIP 2006 普及组] 明明的随机数
题目描述
https://www.luogu.com.cn/problem/P1059
给出 $N(N \lt 10^2)$ 个 $1 \sim 10^3$ 的数字，输出去重后剩余数字的个数以及去重排序后的序列
解法 1：计数排序
在拿到新的选票时发现投票箱中已经有这个选票了，就扔掉这张选票，保持每个票箱中最多只有一张票
最后将有票的票箱编号输出即可
这里要求先输出不同数字的个数，可以先枚举一遍票箱记录，输出剩余数字的个数，然后再枚举一遍票箱，输出序列
也可以创建一个新的数组，在枚举票箱的时候将有票的编号复制进新的数组中
解法 2：STL
当然也可以直接对这些数据进行排序，然后从小到大每个数字只输出一个
考虑数据规模，可以使用上面提到的所有排序方式
不过，这次介绍排序的 STL， 这样就不需要去亲自实现排序算法了
关于 STL，后面可能会出一个专门的专题，STL = Standard Template Library（标准模板库）
有了这个就不用自己手搓了
排序 STL 1：sort
分析
std::sort 被定义于 algorithm 头文件中，因此，你在使用前需要先导入这个头文件，为了方便笔者，笔者会尽可能地在后文省略较多的不影响理解的内容
sort 的基本用法如下
// 形式1：默认升序排序
sort(起始迭代器, 结束迭代器);
// 形式2：自定义比较规则
sort(起始迭代器, 结束迭代器, 比较函数/仿函数/Lambda); // 比较函数即 cmp 用的较多一个例子，sort(a,a+n,cmp)，对 $a[]$ 数组从 $a[0]$ 到 $a[n-1]$ 进行排序，cmp 是指自定义排序函数，如果是将数组 $a[]$ 从小到大排序，那么这一项可以省略
参考代码
#include <iostream>
#include <algorithm>
using namespace std;
int const MAXN = 1010;
int a[MAXN], ans[MAXN], n, cnt = 0, tmp = -1;
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
for (int i = 0; i < n; i++) {
if (a[i] != tmp) ans[cnt++] = a[i]; /* 当前的和上一个不同才复制到新数组 */
tmp = a[i];
}
cout << cnt << endl;
for (int i = 0; i < cnt; i++) cout << ans[i] << ' ';
return 0;
}sort
这里，sort 的时间复杂度是 $O(n \log n)$
如果要对数组 $a[1]$ 到 $a[n]$ 排序，就要用 sort(a+1, a+n+1)
那么，如果要求从大到小排序，只需要定义一个名字是 cmp 的自定义比较函数即可，这个函数的输入是两个元素，如果第一个在第二个之前，则返回 true, 否则返回 false。代码如下：
bool cmp(int q,int h){ // q 前 h 后
return q>h;
}排序 STL 2：unique
分析
std::unqiue 同样被定义于 algorithm 头文件中
unique(a,a+n)：对 $a[]$ 数组从 $a[0]$ 到 $a[n-1]$ 进行去重，要求 $a[]$ 数组已经有序，返回去重后最后一个元素对应的指针
如果使用 unique, 就可以不用 ans 新数组了，可以直接获得去重后的数组和最终元素个数
参考代码
sort(a,a+n);
cnt=unique(a,a+n)-a; // 剩下的数总数
cout<<cnt<<"\n";
for(int i=0;i<cnt;i++) cout<<a[i]<<" ";【题目样本 4.2】P1093 [NOIP 2007 普及组] 奖学金
题目描述
https://www.luogu.com.cn/problem/P1093
有 $n$（$n \le 300$）名学生的语文、数学、英语成绩，这些学生的学号依次是从 $1$ 到 $n$。需要对这些学生进行排序。如果总分相同，则语文分数高者名次靠前；如果语文成绩还相同，学号小者靠前。输出排名前 $5$ 的学生学号和总分
解法 1：STL
分析
定义一个 struct 结构体，命名为 student 存储学生各项信息，使用 sort 附带 cmp 比较函数进行排序，最后输出排序结果，下面是排序优先级
- 总分，高者优先
- 语文，高者优先
- 学好，小者优先
参考代码
#include <algorithm>
#include <iostream>
using namespace std;
int const MAXN = 310;
int n;
struct student {
int id, chinese, total;
} a[MAXN];
int cmp(student a, student b) {
if (a.total != b.total) return a.total > b.total; // 总分先定胜负
if (a.chinese != b.chinese) return a.chinese > b.chinese; // 然后比语文
return a.id < b.id; // 最后比学号
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int math, english;
cin >> a[i].chinese >> math >> english;
a[i].total = a[i].chinese + math + english;
a[i].id = i + 1;
}
sort(a, a + n, cmp);
for (int i = 0; i < 5; i++) {
cout << a[i].id << " " << a[i].total << endl;
}
return 0;
}解法 2：选择排序
分析
时间复杂度 $O(kn)$，此题 $k=5$，即 $O(n)$
解法 3：插入排序
分析
维护排名前 $5$ 数组作为比较对象（手牌）
时间复杂度 $O(n)$，运行效率不高
【题目样本 4.3】P1781 宇宙总统
题目描述
https://www.luogu.com.cn/problem/P1781
共有 ( n )（( n \le 20 )）个非凡拔尖的人竞选总统，现在票数已经统计完毕，请算出谁能够当上总统。第一行输出候选人编号，第二行输出选票数量。票数可能很大，最大会有 100 位
解法 1：计数排序
分析
由于本题只需要求出最大的那一个数字，所以用“打擂台”法
但是数字很大，没办法直接存下来（long long 也存不下）
但是需要高精度，不考虑单开一个话题
解法 2：结构体
分析
存进字符串。不过不能直接对这些字符串进行大小比较，因为字符串比较是比较字典序（第一位小的在前面，如果相同则比较第二位，以此类推），例如 $10000$ 小于 $1200$ 小于 $200$
得手搓 cmp
参考代码
struct node {
string x; // 票数
int num; // 候选人编号
} s[MAXN];
bool cmp(node a, node b) {
if (a.x.length() != b.x.length()) {
return a.x.length() > b.x.length(); // a 比 b 位数多时 a 在前面
}
return a.x > b.x; // 位数相同，但 a 字典序排列比 b 大
}5 汇总
练习
笔者为读者提供了一些洛谷上没有的题目，供练习
C++ 常用排序算法一览表
额外的，这里有一张特别大的表格，供读者查阅
| 排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 最坏空间复杂度 | 稳定性 | 特点 |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | $O(1)$ | ✅ 稳定 | 相邻元素两两比较，大数后移；优化版可提前结束 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | $O(1)$ | ❌ 不稳定 | 每轮选最小放到前面；交换次数最少（n次） |
| 插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | $O(1)$ | ✅ 稳定 | 将元素插入已排序区；数据量小或基本有序时极快 |
| 希尔排序 | $O(n \log n) \sim O(n^2)$ | $O(n \log n)$ | $O(n^2)$ | $O(1)$ | $O(1)$ | ❌ 不稳定 | 分组插入排序；增量序列决定效率 |
| 归并排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | $O(n)$ | ✅ 稳定 | 分治+合并；适合链表和外部排序 |
| 快速排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | $O(n)$ | ❌ 不稳定 | 分治+分区；实际最快，但最坏退化为 $O(n^2)$ |
| 堆排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | $O(1)$ | ❌ 不稳定 | 基于堆数据结构；适合求 Top K |
| 计数排序 | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ | $O(k)$ | $O(k)$ | ✅ 稳定 | 非比较排序；适用于整数且范围 $k$ 不大 |
| 桶排序 | $O(n + k)$ | $O(n + k)$ | $O(n^2)$ | $O(n + k)$ | $O(n + k)$ | ✅ 稳定 | 分桶+桶内排序；数据分布均匀时极快 |
| 基数排序 | $O(d \times (n + k))$ | $O(d \times (n + k))$ | $O(d \times (n + k))$ | $O(n + k)$ | $O(n + k)$ | ✅ 稳定 | 按位排序（LSD/MSD）；适合整数或字符串 |
[collapse status="false" title="C++ 常用排序算法一览表（无特点）"]
| 排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 最坏空间复杂度 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | $O(1)$ | ✅ 稳定 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | $O(1)$ | ❌ 不稳定 |
| 插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | $O(1)$ | ✅ 稳定 |
| 希尔排序 | $O(n \log n) \sim O(n^2)$ | $O(n \log n)$ | $O(n^2)$ | $O(1)$ | $O(1)$ | ❌ 不稳定 |
| 归并排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | $O(n)$ | ✅ 稳定 |
| 快速排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | $O(n)$ | ❌ 不稳定 |
| 堆排序 | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | $O(1)$ | ❌ 不稳定 |
| 计数排序 | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ | $O(k)$ | $O(k)$ | ✅ 稳定 |
| 桶排序 | $O(n + k)$ | $O(n + k)$ | $O(n^2)$ | $O(n + k)$ | $O(n + k)$ | ✅ 稳定 |
| 基数排序 | $O(d \times (n + k))$ | $O(d \times (n + k))$ | $O(d \times (n + k))$ | $O(n + k)$ | $O(n + k)$ | ✅ 稳定 |
[/collapse]
C++ STL 中的排序一览表
同时，这里还有一张关于 STL 的表
| 函数 | 时间复杂度 | 空间复杂度 | 最坏空间复杂度 | 稳定性 | 特点 |
|---|---|---|---|---|---|
std::sort | $O(n \log n)$ | $O(\log n)$ | $O(\log n)$ | ❌ 不稳定 | 混合排序（快排+堆排+插入），最常用 |
std::stable_sort | $O(n \log^2 n) \sim O(n \log n)$ | $O(n)$ | $O(n)$ | ✅ 稳定 | 保证相等元素顺序不变 |
std::partial_sort | $O(n \log k)$ | $O(1)$ | $O(1)$ | ❌ 不稳定 | 取前 $k$ 个最小/最大 |
std::nth_element | $O(n)$ 平均 | $O(1)$ | $O(1)$ | ❌ 不稳定 | 求第 $k$ 小/大，不完全排序 |