设计通用排序库,如何按数据规模选算法
哪些公司问过
阿里蚂蚁金服1
答案要点
- 核心是按规模和特征选算法并组合,典型是内省排序 introsort
- 小规模(约 n<16)用插入排序,常数小、对近乎有序高效
- 主体用快速排序,三数取中或随机选基准,大量重复用三路划分
- 递归过深时切堆排序保底,保证最坏 O(n log n)
- 需要稳定用归并排序,内存放不下用外部排序,接口支持自定义比较器
易错点
- 只用快排不设保底,遇到最坏输入退化成 O(n²)
- 忽视稳定性需求,用不稳定算法排序需要保持相对顺序的数据
- 小数组仍递归快排,增加不必要的递归和分区开销
面试官常见追问
- introsort 是怎么结合三种排序的?
- 为什么小数组用插入排序更好?
- 怎么处理大量重复元素?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场