C++ STL sort自定义排序怎么用

C++ STL 的 sort 允许传入自定义比较函数，用来决定元素的先后顺序。比较函数必须满足严格弱序：对任意元素 a、b，comp(a,b) 和 comp(b,a) 不能同时为真；comp(a,a) 必须为假；并且比较关系要具有传递性。违反严格弱序会导致未定义行为，常见表现是程序在排序过程中崩溃或结果错乱。

自定义排序的核心是提供一个满足严格弱序的比较器。比较器可以是函数指针、函数对象或 lambda，但必须保持无副作用、可重复调用。排序稳定性由 std::stable_sort 保证，std::sort 不保证。若比较逻辑依赖外部可变状态，应将其捕获为值或改用稳定排序，并确保比较期间状态不变。

比较器怎么写：函数、函数对象与 lambda

最简单的写法是普通函数：

bool cmp(int a, int b) { return a > b; }
std::sort(v.begin(), v.end(), cmp);

如果比较需要携带状态（例如按某个字段排序），用函数对象更清晰：

struct CompareByAge {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age;
    }
};
std::sort(people.begin(), people.end(), CompareByAge());

lambda 适合一次性比较，尤其是需要捕获局部变量时：

int pivot = 10;
std::sort(v.begin(), v.end(), [pivot](int a, int b) {
    return std::abs(a - pivot) < std::abs(b - pivot);
});

注意 lambda 捕获的变量在排序期间不应被修改，否则比较器行为不一致，可能破坏严格弱序。

严格弱序的常见坑

写比较器时，最容易犯的错误是返回 a <= b 或 a >= b。这会让 comp(a,a) 为真，违反严格弱序。正确做法是只使用 < 或 >，相等时返回 false。

另一个坑是比较逻辑不满足传递性。例如按绝对值排序时，如果两个数绝对值相等但符号不同，比较器可能对 a、b 返回 true，对 b、c 返回 true，但对 a、c 返回 false。这种比较器在部分数据上可能“看起来正常”，但换一组数据就会触发未定义行为。解决方法是补全相等情况的判断，或者改用稳定排序并确保比较器只依赖一个全序关系。

如果比较器依赖浮点数，注意 NaN 的存在。任何与 NaN 的比较都返回 false，这会破坏严格弱序。排序前应过滤或替换 NaN。

排序稳定性与性能取舍

std::sort 不保证相等元素的相对顺序，平均时间复杂度为 O(N log N)。std::stable_sort 保证稳定性，但可能分配额外内存，时间复杂度也是 O(N log N)，常数通常更大。如果业务要求相等元素保持原有顺序（例如先按分数排序，再按提交时间排序），应使用 std::stable_sort，或者把次要关键字合并进比较器，用一次 std::sort 完成。

比较器应尽量轻量。如果比较逻辑需要频繁计算（例如字符串比较、远程调用），可以预先计算排序键并缓存，或者用 std::sort 配合索引数组，避免在比较器里做重复工作。

验证自定义排序是否正确的清单

检查比较器对相同元素是否返回 false（即 comp(a,a) == false）。
用包含重复元素的测试数据运行，确认没有崩溃或乱序。
用逆序数据测试，确认比较器方向正确。
如果比较器捕获了外部变量，确认排序期间该变量不被修改。
需要稳定性时，确认使用的是 std::stable_sort 而非 std::sort。
在 Debug 构建下开启迭代器调试（如 MSVC 的 _ITERATOR_DEBUG_LEVEL 或 libstdc++ 的 _GLIBCXX_DEBUG），有助于暴露比较器违规。

常见问题

自定义比较器可以返回 `bool` 以外的类型吗？

可以，但返回值必须能隐式转换为 bool。不过建议直接返回 bool，避免隐式转换带来的意外。

排序后想恢复原始顺序怎么办？

如果元素本身没有唯一标识，可以在排序前给每个元素附加原始索引，排序后按索引恢复。或者使用 std::stable_sort 并利用稳定性。