C++ std::sort 的内部实现
哪些公司问过
答案要点
- std::sort 通常采用内省排序(introsort):快速排序加堆排序加插入排序
- 快排递归过深时切换为堆排序,保证最坏 O(n log n)
- 小区间(约 16 个元素以下)改用插入排序
- 要求随机访问迭代器,不保证稳定;需要稳定用 stable_sort
- 具体阈值和实现因标准库而异
易错点
- 说 std::sort 就是纯快速排序
- 忘了小区间的插入排序优化
- 对 list 直接调用 std::sort
- 认为 sort 是稳定的
面试官常见追问
- 快排和堆排的时间复杂度,最坏情况是什么?
- 为什么小区间用插入排序?
- STL 的内存管理方法是怎样的?
- sort 和 stable_sort 有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场
- 取值范围有限的海量数据排序,如考生分数5 场