21. 排序与相关算法：sort、stable_sort、partial_sort、nth_element、binary_search、lower_bound、upper_bound
排序和查找，是日常开发中最基础也最常用的操作。C++ STL 在这方面提供了非常丰富的工具，但很多人只是会用 sort，遇到 partial_sort 或 nth_element 就懵了。今天我把这几个算法串起来讲一遍，希望能帮你理清它们的适用场景。
21.1 sort —— 最常用的全排序
std::sort 用的是内省排序（IntroSort），说白了就是快排 + 堆排的混合体。平均复杂度 O(N log N)，最坏也是 O(N log N)，不会退化到 O(N²)。
#include <algorithm>
#include <vector>
std::vector<int> v = {4, 2, 5, 1, 3};
std::sort(v.begin(), v.end());
// v 变成 {1, 2, 3, 4, 5}默认是升序。想降序？传个 std::greater<>() 就行。
std::sort(v.begin(), v.end(), std::greater<int>());
// v 变成 {5, 4, 3, 2, 1}个人习惯：我一般用 lambda 写比较器，可读性更好。比如按绝对值排序：
std::sort(v.begin(), v.end(), [](int a, int b) {
return std::abs(a) < std::abs(b);
});21.2 stable_sort —— 稳定排序的代价
std::stable_sort 保证相等元素的相对顺序不变。底层是归并排序，需要额外内存。复杂度 O(N log N)，但常数比 sort 大。
什么时候用？比如你先按年龄排序，再按姓名排序，希望年龄相同的记录保持姓名排序的顺序。这时候 stable_sort 就派上用场了。
struct Person {
std::string name;
int age;
};
std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 30}};
std::stable_sort(people.begin(), people.end(),
[](const Person& a, const Person& b) {
return a.age < b.age;
});
// 年龄相同的 Alice 和 Charlie，顺序不变我曾经踩过坑：有一次用 sort 排序一个包含指针的容器，结果两个相同优先级的任务顺序被打乱了，导致后续处理逻辑出错。从那以后，只要涉及「多级排序」，我必用 stable_sort。
21.3 partial_sort —— 只关心前几名
你只需要前 K 个最小的元素，后面的顺序无所谓？用 partial_sort。它会把前 K 个元素排好序，剩下的元素不保证顺序。
std::vector<int> v = {9, 3, 7, 1, 8, 2, 6, 4, 5};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// 前 3 个是 {1, 2, 3}，后面可能是 {9, 8, 7, 6, 5, 4}复杂度 O(N log K)，比全排序快不少。我在做排行榜功能时经常用——只取前 10 名，没必要排全部。
21.4 nth_element —— 快速找到第 K 大的元素
这个算法很特别。它不排序，只保证第 K 个位置上的元素是「如果全排序后应该出现在那个位置的元素」。左边都比它小，右边都比它大，但左右两边内部无序。
std::vector<int> v = {9, 3, 7, 1, 8, 2, 6, 4, 5};
std::nth_element(v.begin(), v.begin() + 4, v.end());
// v[4] 现在是 5（第 5 小的元素）
// 左边 {1, 3, 2, 4} 都小于 5，右边 {6, 7, 8, 9} 都大于 5复杂度 O(N)。你想想看，如果你只需要中位数或者某个分位点，用 nth_element 比 sort 快得多。
避坑指南：我曾经在面试题里看到有人用 sort 找中位数，然后被问「能不能优化」。其实 nth_element 就是标准答案。记住，它不保证排序，只保证分区。
21.5 binary_search —— 二分查找的快速判断
前提：数据必须已经有序。binary_search 返回 bool，告诉你目标值是否存在。
std::vector<int> v = {1, 3, 5, 7, 9};
bool found = std::binary_search(v.begin(), v.end(), 5);
// found == true复杂度 O(log N)。但说实话，这个函数用得不多，因为它只告诉你「有没有」，不告诉你「在哪里」。
21.6 lower_bound 与 upper_bound —— 找到位置才是关键
这两个才是二分查找的利器。
lower_bound：返回第一个 >= 目标值的位置upper_bound：返回第一个 > 目标值的位置
std::vector<int> v = {1, 3, 3, 3, 5, 7};
auto low = std::lower_bound(v.begin(), v.end(), 3);
auto up = std::upper_bound(v.begin(), v.end(), 3);
// low 指向第一个 3（索引 1）
// up 指向 5（索引 4）
// 区间 [low, up) 就是所有值为 3 的元素配合使用，可以快速统计某个值的出现次数：std::distance(low, up)。
我的经验：在写区间查询、日程冲突检测、或者二分答案时，lower_bound 几乎天天用。比如「找到第一个大于等于当前时间的任务」，一行代码搞定。
21.7 知识体系总览
下面这张图帮你理清这几个算法的关系和使用场景：
21.8 综合示例：一个完整的排序+查找场景
假设你有一个学生成绩列表，需要：
- 按分数从高到低排序
- 取出前 5 名
- 查找分数为 85 分的学生是否存在
- 统计 80~90 分的人数
#include <algorithm>
#include <vector>
#include <iostream>
struct Student {
std::string name;
int score;
};
int main() {
std::vector<Student> students = {
{"Alice", 92}, {"Bob", 78}, {"Charlie", 85},
{"David", 85}, {"Eve", 95}, {"Frank", 70}
};
// 1. 按分数降序排序
std::sort(students.begin(), students.end(),
[](const Student& a, const Student& b) {
return a.score > b.score;
});
// 2. 前 5 名（已经排好序了，直接取前 5 个）
std::cout << "Top 5:\n";
for (int i = 0; i < 5 && i < students.size(); ++i) {
std::cout << students[i].name << " - " << students[i].score << "\n";
}
// 3. 查找 85 分是否存在（需要先按分数排序）
std::sort(students.begin(), students.end(),
[](const Student& a, const Student& b) {
return a.score < b.score;
});
bool found = std::binary_search(students.begin(), students.end(), 85,
[](const Student& s, int score) {
return s.score < score;
});
std::cout << "85 分存在吗？" << (found ? "是" : "否") << "\n";
// 4. 统计 80~90 分人数
auto low = std::lower_bound(students.begin(), students.end(), 80,
[](const Student& s, int score) {
return s.score < score;
});
auto up = std::upper_bound(students.begin(), students.end(), 90,
[](const Student& s, int score) {
return s.score < score;
});
int count = std::distance(low, up);
std::cout << "80~90 分人数：" << count << "\n";
return 0;
}核心要点：
sort最快，但不稳定；stable_sort稳定，但慢一点- 只关心前 K 个用
partial_sort，只关心第 K 个用nth_element - 二分查找前必须排序，
lower_bound和upper_bound比binary_search更实用 - 自定义比较器时，注意比较逻辑的一致性——排序和查找要用相同的比较规则
嗯，这些算法其实不难，关键是选对场景。我在实际项目中见过不少人用 sort 全排然后取前几个，其实换成 partial_sort 能省不少时间。多想想你的数据量有多大，你真正需要的是什么，然后选最合适的工具。