用好 std::sort：自定义排序与常见陷阱

想让大的在前面，最简单的办法是传一个 greater<int>() 函数对象（需要 <functional>）：

#include <functional>
sort(v.begin(), v.end(), greater<int>());

当然可以手写比较函数。比如对学生按成绩降序：

struct Student {
    string name;
    int score;
};

bool byScoreDesc(const Student& a, const Student& b) {
    return a.score > b.score;
}

vector<Student> students = {{"Alice", 85}, {"Bob", 90}};
sort(students.begin(), students.end(), byScoreDesc);

任何能接收两个元素并返回 bool 的可调用对象都行，包括 lambda：

sort(students.begin(), students.end(),
     [](const Student& a, const Student& b) { return a.score > b.score; });

复杂规则也能轻松实现，比如按个位数大小排序：

sort(v.begin(), v.end(), [](int a, int b) { return (a % 10) < (b % 10); });

它到底怎么排的

sort() 的实现通常是 Introsort（内省排序）。它从快速排序开始，但当递归深度超过 log₂(n) 的阈值时会切换成堆排序，避免快排退化到 O(n²)；当区间长度小到一定规模（比如 16）时又改用插入排序，利用小数据量下常数开销低的优势。这种混血策略让平均和最坏时间复杂度都稳稳停在 O(n log n)。

最容易踩的坑：比较函数

大部分 sort() 导致的奇奇怪怪崩溃，根因都在比较函数没有满足严格弱序。

严格弱序要求：

• 如果 comp(a,b) 为真，则 comp(b,a) 必须为假（不对称）。
• 传递性：若 comp(a,b) 和 comp(b,c) 都为真，则 comp(a,c) 也必须为真。
• 等价关系：!comp(a,b) && !comp(b,a) 被视为等价（不要求 ==）。

常见错误是用了 <= 或 >=：

// 危险！不满足严格弱序
bool bad(int a, int b) {
    return a <= b;
}

这种比较会让 a 在跟自身或等值元素比较时返回 true，破坏不对称性，可能让元素越界、死循环甚至段错误。正确写法是用 < 或 >，不要带等号。

另一个坑是自定义类型没有重载 operator<，而你又没传比较函数。这时候编译不过，解决方法是给个 lambda 或者重载 <。

适用场景

• 数据处理：想找出销量前几名的商品，按数量降序排一下就出来了。
• 算法题：求第 K 大元素，排序后直接取 v[k-1]（降序）是最快的实现（虽然 nth_element 更合适，但 sort 够简单）。
• 项目里：成绩排名、日志按时间戳排序，都是基本操作。

sort() 本身很皮实，用好它的关键是理解那个比较函数——严格弱序不能妥协，剩下的就是效率上的加分项了。