← 目录 / 第十一章 · STL 标准模板库 / 11.13.1 排序与排列

11.13.1　排序与排列

sort、stable_sort、next_permutation、reverse —— 让数据"换个顺序"的通用算法。

📂 引入头文件：#include <algorithm> —— STL 绝大多数算法都在这里。
本页目录

前面我们学了各种"装数据的箱子"（容器），但光有箱子还不够——我们还需要对箱子里的数据进行排序、查找、反转、计数等等操作。

你可以自己写循环来完成这些任务，但 STL 已经帮你写好了大量经过精心优化的通用算法。这些算法不关心数据在哪种容器里——只要你提供迭代器指定操作范围，它们就能工作。

💡
迭代器范围：STL 算法用一对迭代器来指定操作范围—— [first, last)，表示从 first 开始，到 last 之前为止（last 本身不包含在内）。这和容器的 begin() / end() 完全对应。
① sort —— 排序（最常用的算法）

默认从小到大排序；传入第三个参数可以自定义排序规则（比较函数、greater<T>()、或 lambda 表达式）。

C++ · sort 的几种用法
1#include <algorithm>
2#include <vector>
3using namespace std;
4
5int main()
6{
7 vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
8
9 // 默认从小到大排序
10 sort(v.begin(), v.end());
11 // v 变成 {1, 1, 2, 3, 4, 5, 6, 9}
12
13 // 从大到小排序
14 sort(v.begin(), v.end(), greater<int>());
15 // v 变成 {9, 6, 5, 4, 3, 2, 1, 1}
16
17 // 只排序前 5 个元素
18 sort(v.begin(), v.begin() + 5);
19
20 // 用自定义规则排序（比如按绝对值从小到大）
21 sort(v.begin(), v.end(), [](int a, int b) {
22 return abs(a) < abs(b);
23 });
24
25 return 0;
26}
sort(v.begin(), v.end())；默认从小到大
排序前
3
1
4
1
5
9
2
6
排序后
1
1
2
3
4
5
6
9
相等元素（两个 1）排序后的相对顺序没有保证——如果需要保留原始顺序，要用下面的 stable_sort。
🎯
sort 的时间复杂度是 O(n log n)，比你自己写冒泡排序 O(n²) 快得多。竞赛中几乎所有排序需求都能用它解决。
⚠️
注意：sort 需要随机访问迭代器，所以只能用于 vector、deque、普通数组等。list 没有随机访问能力，要用它自己的成员函数 l.sort()。
② stable_sort —— 稳定排序

稳定排序保证相等元素的相对顺序不变。当排序的依据只是数据的"一部分"（比如只按 pair 的 first 排序）时，稳定排序能保留剩下部分原本的先后关系。

C++ · stable_sort 保留相等元素的原始顺序
1vector<pair<int, string>> v = {{2, "B"}, {1, "A"}, {2, "C"}};
2
3// 按 first 排序
4stable_sort(v.begin(), v.end());
5// 结果：{1, "A"}, {2, "B"}, {2, "C"}
6// 注意：first 相同的两个元素，"B" 和 "C" 保持了原来的先后顺序
💡
sort 平均情况下更快（通常是 introsort，快排+堆排混合），但不保证相等元素的顺序。stable_sort（归并排序实现）多一点时间/空间开销，但顺序稳定。只有当"相等元素的原始顺序对结果有意义"时才需要用 stable_sort，否则 sort 就够了。
③ next_permutation —— 全排列

生成字典序的下一个排列，常用于枚举所有排列。配合 do...while 循环可以遍历某个序列的全部排列方式。

C++ · 枚举 {1,2,3} 的全部排列
1vector<int> v = {1, 2, 3};
2do {
3 for (int x : v) cout << x << " ";
4 cout << endl;
5} while (next_permutation(v.begin(), v.end()));
6// 输出：
7// 1 2 3
8// 1 3 2
9// 2 1 3
10// 2 3 1
11// 3 1 2
12// 3 2 1
⚠️
注意：next_permutation 要求序列初始为升序才能生成全部排列。如果初始不是最小的排列，会漏掉前面的排列。prev_permutation 是它的"反向版本"，生成字典序的上一个排列（这种情况初始序列要是降序才能枚举全部）。
④ reverse —— 反转

把指定范围内的元素整体首尾颠倒。

C++ · reverse 反转整个序列
1vector<int> v = {1, 2, 3, 4, 5};
2reverse(v.begin(), v.end());
3// v 变成 {5, 4, 3, 2, 1}
📌
reverse 同样只需要一对迭代器，可以反转整个容器，也可以只反转一部分区间（比如 reverse(v.begin(), v.begin() + 3) 只反转前 3 个元素）。常用于字符串反转、判断回文等场景。