O(n) 的排序算法(计数、基数、桶排序)
哪些公司问过
答案要点
- 比较排序下限是 O(n log n),线性排序依赖数据本身的特性
- 计数排序 O(n+k),适合值域 k 较小的整数
- 桶排序在数据均匀分布时平均 O(n),分布不均会退化
- 基数排序 O(d(n+b)),每趟必须稳定,int32 可按 8 位分 4 趟
- 负数可翻转符号位或加偏移转成无符号数后再做基数排序
易错点
- 用计数排序处理值域很大的数据,导致内存爆炸
- 基数排序的某一趟使用不稳定的排序
- 忽略负数的处理
- 只看复杂度,忽略常数和缓存效应,不做实测
面试官常见追问
- 为什么比较排序的下限是 O(n log n)?
- 基数排序为什么每趟都要稳定?
- 计数排序为什么不适合值域大的数据?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场