桶排序与快速排序的区别
哪些公司问过
答案要点
- 快排是比较排序,桶排序是非比较排序,依赖值域划分
- 快排平均 O(n log n)、最坏 O(n²);桶排序在分布均匀时平均 O(n+k)
- 快排原地、递归栈 O(log n);桶排序需要 O(n+k) 额外空间
- 快排不稳定;桶排序稳定性取决于桶内排序算法
- 桶排序适合值域已知且均匀分布,快排适合通用场景
易错点
- 说桶排序一定是 O(n),忽略数据分布不均时的退化
- 认为快排空间复杂度是 O(1),忽略递归栈
- 桶的数量和区间划分不合理导致大量空桶或单桶过满
面试官常见追问
- 比较排序的下界是多少?
- 桶排序、计数排序、基数排序什么关系?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场