一万个不重复正整数的最快排序
哪些公司问过
答案要点
- 比较排序下界为 O(n log n),要更快需用非比较排序
- 值域已知时用位图:置位后顺序扫描输出,O(n+M)
- 数字不重复,每个值只需一位,无需计数
- 值域很大时用基数排序,按字节分轮,总体线性
- 规模只有一万时,库排序也足够快,需结合实际说明
易错点
- 不考虑值域就说位图,值域很大时内存不可接受
- 说排序可以做到 O(1) 或低于 O(n)
- 有重复元素时仍用一位的位图,丢失重复数据
面试官常见追问
- 位图需要多少内存?
- 如果要判断某个数是否存在呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场