取值范围有限的海量数据排序,如考生分数
哪些公司问过
答案要点
- 取值范围有限且远小于数据量时,适合计数排序或桶排序
- 计数排序时间复杂度 O(n+k),空间 O(k),优于比较排序的 O(n log n)
- 只排数值时统计次数后按顺序输出即可
- 排带附加信息的记录需前缀和定位,并从后往前放置以保证稳定
- 值域偏移时用值减最小值作下标,如 100 到 900 只需 801 个桶
易错点
- 默认用快排,没注意到值域有限这一关键条件
- 值域很大时也用计数排序,导致计数数组过大
- 排序结构体时只记次数,丢失了记录本身
- 前缀和放置时从前往后遍历,破坏稳定性
面试官常见追问
- 计数排序为什么能突破 O(n log n)?
- 如果分数带小数,比如保留一位小数呢?
- 计数排序和基数排序有什么关系?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场