Appearance
桶排序（Bucket Sort）是一种非比较排序算法，通过将元素分配到多个桶中，每个桶内分别排序，最后按桶顺序合并得到有序数组。适用于数据分布均匀、范围已知的场景，理想情况下时间复杂度可达 O(n)。
定义与核心原理
桶排序的核心思想是分而治之：将数据范围划分为若干个区间（桶），把元素放入对应桶中，桶内排序后按顺序合并。
三步流程
- 分配：遍历数组，将每个元素放入对应的桶
- 排序：对每个桶内的元素分别排序（可用插入排序或快排）
- 合并：按桶的顺序依次取出元素，得到有序数组
操作步骤
以数组 [0.49, 0.96, 0.82, 0.09, 0.57, 0.43, 0.91, 0.75, 0.15, 0.37] 为例：
待排序数组：[0.49, 0.96, 0.82, 0.09, 0.57, 0.43, 0.91, 0.75, 0.15, 0.37]
步骤1：分配到5个桶
桶[0,0.2): [0.09, 0.15]
桶[0.2,0.4): [0.37]
桶[0.4,0.6): [0.49, 0.57, 0.43]
桶[0.6,0.8): [0.75]
桶[0.8,1.0): [0.82, 0.96, 0.91]
步骤2：每个桶内排序
桶[0,0.2): [0.09, 0.15] ✓
桶[0.2,0.4): [0.37] ✓
桶[0.4,0.6): [0.43, 0.49, 0.57]
桶[0.6,0.8): [0.75] ✓
桶[0.8,1.0): [0.82, 0.91, 0.96]
步骤3：按桶顺序合并
结果：[0.09, 0.15, 0.37, 0.43, 0.49, 0.57, 0.75, 0.82, 0.91, 0.96]复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好 | O(n + k) | 数据均匀分布，每个桶元素少 |
| 平均 | O(n + k) | k 为桶的数量 |
| 最坏 | O(n²) | 所有元素集中在一个桶 |
| 空间 | O(n + k) | 桶的额外空间 |
实践应用
- 浮点数排序：数据在 [0,1) 范围内均匀分布时效率极高
- 基数排序的前置步骤：桶排序可作为基数排序的子过程
- 外部排序：大数据量无法全部载入内存时，分桶处理
- 成绩排序：已知分数范围 0-100，分 101 个桶实现 O(n) 排序
常见误区
- 桶数量设置不当：桶太少 → 每个桶元素多，排序慢；桶太多 → 空间浪费
- 数据分布不均：数据集中在少数桶时退化为 O(n²)，需动态调整桶大小
- 桶内排序算法选择：桶内元素少时用插入排序（O(k²) 但常数小），元素多时用快排
一句话总结
桶排序是非比较排序：按值域分桶、桶内各自排序后按桶序拼接，数据均匀分布时达 O(n+k)；元素全挤进一个桶就退化成 O(n²)。