C++怎么实现排序算法_C++算法实战教程【经典】

std::sort 不能直接排自定义类型，因为默认使用 operator

std::sort 为什么不能直接排自定义类型

因为 std::sort 默认用 比较，而你的类/结构体没定义这个运算符，编译会报错：<code>invalid operands to binary expression。

• 最简解法：给类加 operator 成员函数，返回 <code>bool
• 不想改类？传第三个参数——一个 lambda 或函数对象，比如 std::sort(v.begin(), v.end(), [](const auto& a, const auto& b) { return a.id
• 注意 lambda 捕获列表为空（[ ]），带 & 或 = 可能引发意外绑定或生命周期问题

手写快排时 partition 函数边界总出错

90% 的手写错误集中在 while 循环条件和指针移动顺序上，比如死循环、越界访问或漏交换。

• 统一用左闭右开区间 [l, r)，pivot 选 arr[l]，初始化 i = l + 1, j = r - 1
• 内层 while 必须先检查边界再访问数组：写成 while (i ，而不是 <code>while (arr[i]
• 交换后别忘了继续移动指针，否则可能原地打转；最后记得把 pivot 换到 i - 1 位置

stable_sort 比 sort 慢但必须用的场景

当数据本身有隐含顺序（比如按时间戳插入的记录），且你只想按某字段重排、又不希望相同字段的元素相对位置改变时，std::stable_sort 是唯一选择。

• std::sort 不保证稳定性，std::stable_sort 时间复杂度通常是 O(n log n)，但空间开销更大（可能达 O(n)）
• 对 std::list 或 std::forward_list，只能用 list::sort()——它是稳定且原地的，但接口不同，不接受随机迭代器
• 如果只是临时稳定排序少量数据，考虑用 std::vector<:pair original_index>></:pair> 辅助，避免额外内存分配

sort 在 vector 上编译失败

std::vector<bool></bool> 是特化模板，它的 iterator 不是真正的随机访问迭代器，std::sort 依赖的某些操作（如 iter + n）不满足要求，会触发 SFINAE 失败或编译错误。

立即学习“C++免费学习笔记（深入）”；

• 立刻换成 std::vector<char></char> 或 std::vector<int></int>，哪怕只存 0/1，也能正常用 std::sort
• 真要处理布尔序列且需排序逻辑？先用 std::count 统计 true 个数，再用 std::fill 填充前段为 true，后段为 false——O(n) 且无迭代器问题
• 别试图 cast 迭代器或写 traits 修复，得不偿失

事情说清了就结束