桶排序 (Bucket Sort)
将数组分到有限数量的桶里，每个桶分别排序，最后合并结果的非比较排序算法。
定义
桶排序（Bucket Sort） 是一种非比较排序算法，其核心思想是：将数组分到有限数量的桶里，每个桶再分别进行排序（可以使用其他排序算法或递归使用桶排序），最后按桶的顺序合并结果。
核心特性
| 特性 | 说明 |
|---|---|
| 排序类型 | 非比较排序 |
| 平均时间复杂度 | O(n + k)，k 为桶数量 |
| 最坏时间复杂度 | O(n²)，所有元素落入同一桶 |
| 空间复杂度 | O(n + k) |
| 稳定性 | 取决于桶内排序算法 |
| 适用场景 | 数据分布均匀，可预测范围 |
基本原理
算法步骤
- 创建桶：根据数据范围创建 k 个桶
- 分配元素：遍历数组，将每个元素放入对应的桶
- 桶内排序：对每个非空桶进行排序（可用插入排序、快排等）
- 合并结果：按桶顺序将元素复制回原数组
简单示例
对 [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68] 进行桶排序：
桶0 [0.17, 0.12, 0.21, 0.23]
桶1 [0.39, 0.26]
桶2 []
桶3 []
桶4 []
桶5 []
桶6 [0.68]
桶7 [0.78, 0.72]
桶8 []
桶9 [0.94]
桶内排序后合并：[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]
时间复杂度/性能
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 平均情况 | O(n + k) | 数据分布均匀，每个桶元素少 |
| 最坏情况 | O(n²) | 所有元素落入同一桶 |
| 空间占用 | O(n + k) | 桶 + 元素存储 |
关键点：桶排序的效率高度依赖数据的分布和桶数量的选择。
与类似概念对比
| 维度 | 桶排序 | 计数排序 | 基数排序 |
|---|---|---|---|
| 排序类型 | 非比较排序 | 非比较排序 | 非比较排序 |
| 时间复杂度 | O(n + k) 平均 | O(n + k) | O(d * (n + k)) |
| 数据要求 | 分布均匀 | 整数，范围小 | 整数或可映射 |
| 与计数排序关系 | 通用形式 | 特例（每桶一种值） | 使用计数排序作为子过程 |
| 稳定性 | 取决于桶内排序 | 可稳定 | 必须稳定 |
常见实现要点
- 桶数量选择：通常 k = n（元素个数），或根据数据范围计算
- 映射函数：如何将元素映射到桶，
bucketIndex = (int)(num * k) - 桶内排序：小数组用插入排序，大数组用快排或递归桶排序
注意事项
- 数据分布要求高：如果数据分布不均匀，效率会大幅下降
- 不适合所有场景：对于未知分布或分布极差的数据，效果不好
- 桶数量选择：太少导致桶内元素多，太多导致空间浪费
应用场景
- 外部排序（数据量太大无法一次性加载）
- 数据分布可预测的场景
- 作为基数排序的对比概念