c++oding="utf-8" ?>
std::sort 不稳定因其默认使用快排、堆排等不稳定算法，而 std::stable_sort 强制采用归并策略以保持相等元素的原始顺序；二者时间复杂度均为 O(n log n)，但后者空间复杂度为 O(n)。
std::sort 为什么不能保证稳定，而 std::stable_sort 可以
因为 std::sort 默认用的是 introsort（内省排序）：小数组用插入排序，中等规模用堆排序，大数组用快速排序。快排和堆排本身就不稳定，交换不保序；std::stable_sort 则强制采用归并策略（或优化的缓冲归并），所有合并操作都保持相等元素的原始相对位置。
常见错误现象：std::sort 后，相同 key 的结构体顺序乱了，比如按分数排序后，同分学生的提交时间顺序丢失。
- 使用场景：需要二次排序（如先按班级、再按成绩）时，必须用
std::stable_sort对第二关键字排序，才能保留第一关键字的组内顺序 - 性能影响：
std::stable_sort平均时间复杂度仍是 O(n log n)，但空间开销更大（通常需 O(n) 额外内存），而std::sort是就地排序，空间 O(log n) - 兼容性注意：某些嵌入式 STL 实现（如 libstdc++ 的 -Os 编译模式）可能降级为非稳定归并，但行为仍符合标准要求
手写快排时怎么加稳定化补丁
原生快排无法稳定——核心问题在 partition 过程中，把等于 pivot 的元素随机甩到左右两边。要“伪稳定”，只能放弃原地性，用额外容器记录原始索引，或改用三路划分 + 索引绑定。
实操建议：真需要稳定且不想用 std::stable_sort，直接手写归并排序更可靠；若坚持快排思路，至少做到：
- 给每个元素绑定原始下标（例如用
std::pair），比较逻辑里加入下标兜底：a.first - 避免用
std::partition，自己写三路划分，并把 == pivot 的元素统一存入临时 vector，最后拼接 - 别试图在原数组上“局部稳定”——快排的递归交换天然破坏局部顺序，补丁成本远超重写
自定义比较函数写错导致排序结果诡异的典型原因
最常踩的坑不是逻辑错，而是违反严格弱序（strict weak ordering）。只要比较函数返回 true 表示 “a 应该排在 b 前面”，就必须满足：反身性（comp(a,a) 永远 false）、反对称性（comp(a,b) 和 comp(b,a) 不同时 true）、传递性（comp(a,b)&&comp(b,c) ⇒ comp(a,c)）。
错误示例：[&](const auto& a, const auto& b) { return a.key —— 让 comp(a,a) 返回 true，直接触发 undefined behavior，可能 crash 或静默错排。
- 永远用
，不要用、!=、>写比较逻辑 - 浮点数比较必须带 epsilon，但不能直接写
abs(a-b) 作为比较函数——它不满足传递性；应先判断是否“相等”，再 fallback 到其他字段 - lambda 捕获引用时注意生命周期：如果
comp存活时间超过被捕获对象，运行时可能读到野值
小数组（n
值得，而且编译器不会帮你自动优化到这个粒度。现代 std::sort 实现（如 libc++ 和 libstdc++）确实内置了阈值切换，但仅限于内部调用路径；你自己写的排序主循环若没设阈值，小数据量反而因函数调用/分支预测失败更慢。
实操建议：不管用哪种主算法，都在递归或迭代入口加长度判断：
- 当
end - begin ，直接调用insertion_sort(begin, end)（手写 4~5 行即可） - 插入排序的内层循环用
而非，避免越界访问；移动元素时用std::move（对非 POD 类型） - 别迷信“汇编级优化”：对小数组，分支预测失败比少一次比较代价高得多，宁可多比一次，也要减少条件跳转
稳定性和性能的真正取舍点不在算法名字上，而在你是否清楚每一步内存访问模式和比较谓词的数学性质。很多“自己实现更快”的错觉，其实来自没测对 baseline，或者把调试版和 release 版混在一起比。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
