排序与分区算法：sort, stable_sort, partial_sort, nth_element, partition, stable_partition
排序和分区，是日常开发里最常用的算法之一。说实话，很多人对排序的理解就停留在「调用 sort 完事」。但实际项目中，场景千差万别——有的数据量大到不能全排，有的要求稳定排序，有的只需要把前几名挑出来。这时候，选对算法比写对代码更重要。
我个人习惯把这一组算法分成两类：排序家族和分区家族。它们解决的问题不同，但底层逻辑相通。今天我们就一个一个掰开来看。
核心要点：排序算法不只有 sort，分区算法也不只是 partition。理解每个算法的「适用边界」，才能写出高性能代码。
1. sort —— 最常用的全排序
std::sort 是 C++ 标准库里最基础的排序函数。它底层用的是 内省排序（IntroSort）—— 快速排序 + 堆排序的混合体。平均复杂度 O(N log N)，最坏情况也是 O(N log N)。
我在项目中遇到过一个问题：有个同事用 sort 对 10 万个结构体排序，结果每次运行时间都不稳定。后来发现是自定义比较器里拷贝了很大的对象。改成传引用后，速度直接快了 3 倍。嗯，这里要注意——比较器一定要用 const 引用。
#include <algorithm>
#include <vector>
std::vector<int> data = {4, 2, 5, 1, 3};
std::sort(data.begin(), data.end());
// data 变为 {1, 2, 3, 4, 5}
// 自定义比较器（降序）
std::sort(data.begin(), data.end(), std::greater<int>());
// data 变为 {5, 4, 3, 2, 1}小技巧：如果容器是 std::list，不要用 sort——list 有自己的成员函数 list::sort()，效率更高。
2. stable_sort —— 稳定排序的担当
std::stable_sort 保证相等元素的相对顺序不变。它底层用的是 归并排序，所以需要额外的内存。复杂度 O(N log N)，但常数比 sort 大。
你想想看，什么时候需要稳定排序？比如按成绩排序，成绩相同的人要保持原来的学号顺序。这时候 stable_sort 就派上用场了。
struct Student {
int score;
int id;
};
std::vector<Student> students = {{85, 3}, {92, 1}, {85, 2}};
std::stable_sort(students.begin(), students.end(),
[](const Student& a, const Student& b) {
return a.score > b.score;
});
// 结果：{92,1}, {85,3}, {85,2} —— 85分的保持了原来的 id 顺序注意：stable_sort 会额外分配内存。如果内存紧张，可以考虑用 sort + 自定义比较器来模拟稳定排序（比如比较时加入次要字段）。
3. partial_sort —— 只排前几名
有时候我们只需要前 10 个最大的数，后面的顺序无所谓。这时候用 std::partial_sort 最合适。它会把前 N 个元素排好序，剩下的元素不保证顺序。
我记得有一次做排行榜功能，用户量很大，每次都要从 100 万条数据里取前 100 名。如果用 sort 全排，太浪费了。换成 partial_sort 后，性能提升很明显。
std::vector<int> data = {10, 3, 7, 1, 9, 4, 6, 2, 8, 5};
std::partial_sort(data.begin(), data.begin() + 3, data.end(), std::greater<int>());
// 前3个元素是 {10, 9, 8}，后面的顺序不确定性能对比：partial_sort 的复杂度是 O(N log K)，其中 K 是你要排序的元素个数。当 K 远小于 N 时，优势非常明显。
4. nth_element —— 找到第 N 大的元素
std::nth_element 是个很有意思的算法。它不排序，只保证第 N 个位置上的元素是「正确」的——也就是说，它左边的元素都小于等于它，右边的都大于等于它。复杂度 O(N)。
说白了，它就是快速排序里的 partition 步骤。如果你只需要中位数、或者第 90 百分位数，用 nth_element 比排序快得多。
std::vector<int> data = {7, 2, 9, 1, 5, 8, 3, 6, 4};
std::nth_element(data.begin(), data.begin() + 4, data.end());
// data[4] 就是第5小的元素（即中位数），左边都比它小，右边都比它大实战经验：我在做数据分桶时，经常用 nth_element 来找到分位点。比如把 100 万条数据分成 10 个桶，只需要调用 9 次 nth_element 就能找到所有分位点。
5. partition —— 快速分区
std::partition 根据一个谓词把区间分成两部分：满足条件的在前，不满足的在后。它返回一个迭代器，指向第一个不满足条件的元素。
这个函数在「筛选」场景下特别好用。比如把及格和不及格的学生分开，或者把奇数和偶数分开。
std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8};
auto it = std::partition(data.begin(), data.end(),
[](int x) { return x % 2 == 0; });
// data 变为 {2, 4, 6, 8, 1, 3, 5, 7}
// it 指向 1（第一个奇数）注意：partition 是不稳定的——相等元素的相对顺序可能会变。如果你需要保持顺序，用 stable_partition。
6. stable_partition —— 稳定的分区
std::stable_partition 和 partition 功能一样，但它保证相等元素的相对顺序不变。代价是需要额外的内存，复杂度仍然是 O(N)。
我曾经在日志处理中用过它：需要把错误日志和普通日志分开，但又要保持时间顺序。stable_partition 正好满足需求。
std::vector<std::string> logs = {"INFO: start", "ERROR: crash", "INFO: running", "ERROR: timeout"};
auto it = std::stable_partition(logs.begin(), logs.end(),
[](const std::string& s) { return s.find("ERROR") == 0; });
// logs 变为 {"ERROR: crash", "ERROR: timeout", "INFO: start", "INFO: running"}
// 错误日志在前，且保持了原来的相对顺序总结对比表
| 算法 | 复杂度 | 稳定性 | 额外内存 | 适用场景 |
|---|---|---|---|---|
| sort | O(N log N) | 否 | 否 | 通用全排序 |
| stable_sort | O(N log N) | 是 | 是 | 需要保持相等元素顺序 |
| partial_sort | O(N log K) | 否 | 否 | 只排前 K 个 |
| nth_element | O(N) | 否 | 否 | 找第 N 大/中位数 |
| partition | O(N) | 否 | 否 | 快速二分 |
| stable_partition | O(N) | 是 | 是 | 稳定二分 |
我的建议：不要一上来就用 sort。先问自己三个问题——需要全排吗？需要稳定吗？数据量有多大？想清楚了再选算法。很多时候，nth_element 或 partial_sort 就能解决问题，何必杀鸡用牛刀呢？