std::sort 比较函数只写小于时相等元素怎么处理
哪些公司问过
答案要点
- comp 只需返回 a.index < b.index;相等时两个方向都为 false,即视为等价
- 比较函数须满足严格弱序:非自反、非对称、可传递,等价关系也可传递
- std::sort 不稳定,等价元素相对顺序不保证;需保持顺序用 std::stable_sort
- 写成 <= 违反严格弱序,属于未定义行为,实际可能越界或崩溃
- C++11 起 std::sort 保证 O(n log n),常见实现为内省排序
易错点
- 为照顾相等情况把 < 改成 <=,反而引入未定义行为
- 以为 std::sort 会保留相等元素的原始顺序
- 比较浮点数时遇到 NaN,同样会破坏严格弱序
面试官常见追问
- 为什么写成 <= 可能崩溃?
- index 相同时想再按 name 排怎么写?
- stable_sort 的代价是什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场