桶排序如何设计桶的数量和映射函数？
简化版
桶排序把元素按范围分到多个桶里，桶内再排序，最后按桶顺序合并。
桶的数量和映射函数会直接影响性能。如果数据分布均匀，桶排序可以接近 O(n)；如果大量元素落到同一个桶，就会退化成桶内排序的成本。
所以桶排序的关键不是“有桶就快”，而是桶划分要匹配数据分布。
详细版
桶排序流程：
- 根据元素值计算桶编号；
- 把元素放入对应桶；
- 对每个桶内部排序；
- 按桶顺序拼接结果。
bucketIndex = floor((x - minVal) / bucketSize)| 参数 | 影响 |
|---|---|
| 桶数量 | 并行度和空桶数量 |
| 桶大小 | 每个桶覆盖范围 |
| 映射函数 | 数据是否均匀分布 |
| 桶内排序 | 决定退化成本 |
它适合数据分布比较均匀、范围可估计的场景。
完整版教学
1. 桶排序和计数排序的区别
计数排序通常每个具体值对应一个计数位置。
桶排序则是每个桶覆盖一个范围，桶内可以有多个不同值。
| 算法 | 分组粒度 |
|---|---|
| 计数排序 | 每个值 |
| 桶排序 | 每个范围 |
因此桶排序更依赖数据分布和桶设计。
2. 桶排序的基本流程
标准流程如下：
create buckets
for x in nums:
put x into bucket[index(x)]
for bucket in buckets:
sort(bucket)
concat buckets如果桶覆盖的范围有序，那么按桶编号从小到大拼接就能得到全局有序结果。
桶排序的正确性来自：小编号桶里的元素都不大于大编号桶里的元素。
3. 如何设计映射函数
如果已知最小值 minVal 和桶大小 bucketSize，常见映射是：
idx = (x - minVal) / bucketSize如果数据是 [0, 1) 区间的小数，也常见：
idx = floor(x * bucketCount)映射函数要保证两个条件：
- 所有元素都能映射到合法桶；
- 桶之间的顺序和数值大小一致。
4. 桶数量怎么选
桶太少，每个桶很大，桶内排序成本高。
桶太多，空桶多，空间和初始化成本上升。
| 桶数量 | 影响 |
|---|---|
| 太少 | 桶内元素多，退化明显 |
| 适中 | 分布均衡，效率好 |
| 太多 | 空间浪费，管理成本高 |
常见经验是让桶数量和元素数量同阶，但具体还要看值域和分布。
5. 为什么分布不均会退化
桶排序理想情况是元素均匀落入各桶。
如果所有元素都落到同一个桶，就变成：
对一个大桶做排序这时性能取决于桶内排序算法，可能退回 O(n log n)。
所以桶排序常用于分布比较均匀的数据，而不是任意数据。
6. 桶内排序怎么选
桶内元素通常较少，可以选择简单排序。
| 桶内规模 | 可选方案 |
|---|---|
| 很小 | 插入排序 |
| 中等 | 快排或归并 |
| 需要稳定 | 稳定排序 |
| 桶内值域小 | 计数排序 |
如果桶排序要求整体稳定，桶内排序也要稳定，并且入桶顺序不能被破坏。
7. 复杂度怎么回答
理想情况下，分布均匀，桶内排序成本很小，整体接近：
O(n + bucketCount)最坏情况下，所有元素落入同一个桶，如果桶内用比较排序，可能是：
O(n log n)如果桶内用插入排序，还可能在极端情况下变成 O(n^2)。
8. 常见误区与追问
- 误区：桶排序一定是线性时间。 只有分布合适、桶内成本可控时才接近线性。
- 误区：桶越多越好。 桶太多会浪费空间，也会增加管理成本。
- 误区：桶内不需要排序。 同一个桶里仍可能有多个不同值，需要桶内有序。
- 追问：桶排序适合什么数据？ 值域可估计、分布较均匀的数据。
- 追问：如何保证整体有序？ 映射函数要让小桶范围整体小于大桶范围，再按桶序拼接。