C++ std::sort() 排序详解
（2025-2026 年最实用、最清晰版本，适合从入门到面试/工程使用）
一、std::sort 最核心一句话
std::sort(首迭代器, 尾迭代器[, 比较函数/仿函数/lambda]);- 默认升序排序（从小到大）
- 原地排序（直接修改原容器，不产生新空间）
- 不稳定排序（相同元素的相对顺序可能改变）
- 时间复杂度：平均/最坏 O(n log n)（内省排序 + 插入排序混合）
二、最常用的 6 种写法（按使用频率排序）
#include <algorithm> // 必须包含
#include <vector>
#include <functional> // greater<>, less<> 等
using namespace std;1. 最简单：对 vector 整体升序
vector<int> v = {5, 2, 9, 1, 5, 6};
sort(v.begin(), v.end());
// 结果：1,2,5,5,6,92. 降序排序（最常见面试写法）
// 写法一：用 greater<>
sort(v.begin(), v.end(), greater<int>());
// 写法二：用 lambda（C++11+ 推荐）
sort(v.begin(), v.end(), [](int a, int b){ return a > b; });
// 写法三：greater<>{}（C++14+ 最简洁）
sort(v.begin(), v.end(), greater<>{});3. 对部分区间排序
// 只排序下标 2 到 5（不包含 5）
sort(v.begin()+2, v.begin()+5);4. 自定义比较规则（结构体/类对象排序最常用）
struct Student {
string name;
int score;
int age;
};
// 按分数降序，分数相同按年龄升序
sort(v.begin(), v.end(), [](const Student& a, const Student& b){
if (a.score != b.score) return a.score > b.score;
return a.age < b.age;
});5. 按多个维度排序（最实用写法）
// 按身高降序，身高相同按体重升序
sort(players.begin(), players.end(),
[](const auto& a, const auto& b){
return a.height != b.height ? a.height > b.height : a.weight < b.weight;
});6. 配合 greater/less 排序 pair/first/second
vector<pair<int, string>> vp;
// 按 first 降序
sort(vp.begin(), vp.end(), greater<pair<int,string>>());
// 只按 second 升序（忽略 first）
sort(vp.begin(), vp.end(),
[](const auto& a, const auto& b){ return a.second < b.second; });三、std::sort vs 其他排序函数对比（面试高频）
| 函数 | 是否稳定 | 时间复杂度 | 是否原地 | 适用场景 | 推荐度 |
|---|---|---|---|---|---|
std::sort | 否 | O(n log n) | 是 | 绝大多数情况首选 | ★★★★★ |
std::stable_sort | 是 | O(n log n) | 是 | 需要保持相同元素相对顺序时 | ★★★★☆ |
std::partial_sort | — | O(n log k) | 是 | 只想得到前 k 个最小/最大元素 | ★★★☆☆ |
std::nth_element | — | 平均 O(n) | 是 | 找第 k 大/第 k 小（快选思想） | ★★★☆☆ |
四、std::sort 的底层实现（了解即可，面试加分）
现代主流实现（libstdc++ / libc++ / MSVC）几乎都用：
Introsort（内省排序） = QuickSort + HeapSort + InsertionSort 的混合体
- 小规模（<16 或 32 个元素）→ 插入排序（最快）
- 深度过深（防止最坏情况）→ 切换为堆排序
- 普通情况 → 三路快速排序 / 双指针快速排序
所以才保证了平均和最坏都是 O(n log n)
五、常见踩坑 & 最佳实践（工程必看）
- 千万不要在比较函数里修改元素！
// 错误！比较函数必须是严格弱序（strict weak ordering）
sort(v.begin(), v.end(), [](int a, int b){ v[0]++; return a < b; });- 比较函数要满足严格弱序（不能有 a < b 且 b < a 同时成立） 经典错误：
// 错误：浮点数比较 + 等于情况处理不当
sort(v.begin(), v.end(), [](double a, double b){ return a <= b; });正确：
return a < b; // 或者用 std::less<> 等- 大对象排序建议用索引排序（避免大量元素移动）
vector<string> names = {...}; // 很长的字符串
vector<int> idx(names.size());
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j){
return names[i] < names[j];
});- C++20 ranges 写法（越来越流行）
#include <ranges>
ranges::sort(v); // 默认升序
ranges::sort(v, ranges::greater{}); // 降序六、快速记忆口诀
- 想快、不在乎顺序 →
sort（默认） - 想保持相同元素相对顺序 →
stable_sort - 想排序前 k 个 →
partial_sort - 想找第 k 大/小 →
nth_element - 自定义规则 → lambda 或仿函数（最灵活）
一句话总结：
std::sort 是 C++ 中最快、最通用、出现频率最高的排序函数，几乎所有需要排序的场景都应该优先考虑它。
有具体场景想看完整代码示例吗？
比如：
- 结构体多字段排序
- pair / tuple 排序
- 字符串按长度 + 字典序
- 降序 + 去重组合使用
- ranges 版本写法
随时告诉我～
