C++ sort函数怎么自定义排序 C++标准库排序算法实战教程【应用】

std::sort自定义排序要求比较函数满足严格弱序，因其是算法正确性的数学前提；若违反传递性或反对称性（如误写为a

直接说结论：用 std::sort 自定义排序，核心就是传一个可调用对象（函数指针、lamb

da 或重载了 operator() 的仿函数），它接收两个同类型参数，返回 true 表示“第一个应排在第二个前面”。

为什么传的比较函数必须是“严格弱序”？

这不是语法限制，而是算法正确性的数学前提。如果比较逻辑不满足传递性或反对称性（比如写成 a ），std::sort 可能崩溃、无限循环，或产生乱序结果——尤其在 libstdc++ 或 libc++ 的 introsort 实现中容易触发断言失败。

常见翻车点：

• 用 或 != 替代
• 对浮点数直接用 比较（未处理 NaN）
• 在 lambda 中修改外部变量，导致多次调用行为不一致

lambda 是最常用也最安全的写法

适用于临时、局部、逻辑简单的排序，避免函数命名污染和头文件依赖。

例如按 std::vector 长度降序排列：

std::vector> vecs = {{1,2}, {3}, {4,5,6,7}};
std::sort(vecs.begin(), vecs.end(), [](const auto& a, const auto& b) {
    return a.size() > b.size(); // 注意：这里是 >，不是 >=
});

关键细节：

• 捕获列表用空 []，除非真要访问外部变量
• 参数用 const auto& 避免拷贝，尤其对大对象
• 返回类型自动推导，无需写 -> bool
• 不能用 return a —— 严格弱序只允许 类语义

什么时候该写独立比较函数或仿函数？

当排序逻辑复用性强、需测试、或涉及复杂状态（比如带权重的多级比较）时，比 lambda 更清晰。

例如按字符串长度升序，等长时按字典序降序：

struct CustomCmp {
    bool operator()(const std::string& a, const std::string& b) const {
        if (a.length() != b.length()) return a.length() < b.length();
        return a > b; // 字典序降序
    }
};
// 使用：
std::sort(v.begin(), v.end(), CustomCmp{});

注意点：

• 加 const 成员函数 + const 参数，避免意外修改
• 构造函数带参数？可以，但 std::sort 要求可默认构造或能复制（所以一般不用带参构造）
• 函数名不重要，关键是类型可传入第三个模板参数位置

别忘了 std::stable_sort 和自定义的兼容性

如果排序后需保持相等元素的原始相对顺序（比如先按分数排，再按提交时间稳定排序），就换用 std::stable_sort，它接受的比较函数签名和 std::sort 完全一样，行为也一致，只是稳定性有保证。

性能差异：通常慢 10%–30%，内存开销略高，但逻辑正确性优先时没得选。

容易被忽略的一点：自定义比较函数里千万别调用 std::sort 自身——递归调用不会报错，但会因迭代器失效或重复计算导致未定义行为。