桶排序的原理与实现
哪些公司问过
答案要点
- 按值域把数据分到若干桶,桶内单独排序,再按顺序合并
- 步骤:找最值确定桶区间,映射入桶,桶内排序,按序合并
- 均匀分布时平均 O(n+k);分布极不均匀时退化,插入排序最坏 O(n²)
- 空间 O(n+k),稳定性取决于桶内排序算法
- 适合分布均匀、范围已知的数据,也是海量数据分治排序的思路
易错点
- 说桶排序在任何数据上都是 O(n)
- 忘了桶内还需要排序
- 说桶排序一定稳定
面试官常见追问
- 桶排序和计数排序、基数排序有什么关系?
- 桶的数量怎么定?
- 数据分布不均匀怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场