桶排序（Bucket Sort）
桶排序真正赌的是“数据分布够均匀”。一旦元素能比较平均地落进各个桶，整体排序就会非常快。
定义
桶排序是一种分配排序算法，将数据分配到有限数量的桶中，每个桶再分别排序（可以使用其他排序算法或递归使用桶排序），最后按顺序合并所有桶中的数据。
核心思路
- 设置固定数量的空桶
- 将数据分配到对应的桶中
- 对每个非空桶进行排序
- 按顺序合并所有桶中的数据
原数组: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
范围: [0, 1)
创建10个桶:
bucket[0]: []
bucket[1]: [0.17, 0.12]
bucket[2]: [0.26, 0.21, 0.23]
bucket[3]: [0.39]
bucket[4]: []
bucket[5]: []
bucket[6]: [0.68]
bucket[7]: [0.78, 0.72]
bucket[8]: []
bucket[9]: [0.94]
每个桶排序后:
bucket[1]: [0.12, 0.17]
bucket[2]: [0.21, 0.23, 0.26]
bucket[3]: [0.39]
bucket[6]: [0.68]
bucket[7]: [0.72, 0.78]
bucket[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+k) | k是桶的数量 |
| 最坏时间 | O(n²) | 所有数据在一个桶中 |
| 空间复杂度 | O(n+k) | 需要额外的桶空间 |
| 稳定性 | ✅ 稳定 | 取决于桶内排序算法 |
适用条件：
- 数据均匀分布
- 数据范围已知
Go 代码
Go 实现
package main
import (
"fmt"
"sort"
)
func insertionSort(arr []float64) {
for i := 1; i < len(arr); i++ {
key := arr[i]
j := i - 1
for j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
func bucketSort(arr []float64) []float64 {
if len(arr) == 0 {
return arr
}
n := len(arr)
buckets := make([][]float64, n)
// 分配到桶
for _, num := range arr {
index := int(num * float64(n))
if index == n {
index--
}
buckets[index] = append(buckets[index], num)
}
// 对每个桶排序
result := make([]float64, 0, n)
for _, bucket := range buckets {
if len(bucket) > 0 {
insertionSort(bucket)
result = append(result, bucket...)
}
}
return result
}
func main() {
arr := []float64{0.78, 0.17, 0.39, 0.26, 0.72,
0.94, 0.21, 0.12, 0.23, 0.68}
fmt.Println("原始数组:", arr)
sorted := bucketSort(arr)
fmt.Println("排序后:", sorted)
}易错点
桶排序的核心不是代码，而是桶怎么设计。
- 桶数太少，桶内元素太多，退化明显。
- 桶数太多，空间浪费，管理开销也会上去。
- 桶边界要统一成左闭右开还是别的形式，不能含糊。
- 桶内排序最好选简单稳定的小规模排序，比如 插入排序。
算法优化
经典题目
基础应用
桶的应用
- 前K个高频元素 - LeetCode 347
- 存在重复元素 III - LeetCode 220
区间问题
- 在 D 天内送达包裹的能力 - LeetCode 1011
优缺点
优点
- ✅ 线性时间：当数据均匀分布时，O(n+k)
- ✅ 稳定排序：使用稳定的桶内排序
- ✅ 适合外部排序：可以分批处理
- ✅ 并行友好：各桶可以并行排序
缺点
- ❌ 空间复杂度高：需要额外的桶空间
- ❌ 性能不稳定：依赖数据分布
- ❌ 需要预知范围：需要知道数据范围
- ❌ 桶数量难确定：桶太少或太多都影响性能
应用场景
- 均匀分布数据：数据分布均匀
- 浮点数排序：[0, 1)区间的浮点数
- 外部排序：数据量大，内存有限
- 并行排序：利用多核CPU
桶排序 vs 其他排序
| 特性 | 桶排序 | 计数排序 | 基数排序 |
|---|---|---|---|
| 时间复杂度 | O(n+k) | O(n+k) | O(d×(n+k)) |
| 适用数据 | 均匀分布 | 小范围整数 | 整数/字符串 |
| 空间复杂度 | O(n+k) | O(k) | O(n+k) |
| 稳定性 | 稳定 | 稳定 | 稳定 |
如何选择桶的数量
桶的数量影响性能：
- 太少：每个桶元素多，桶内排序慢
- 太多：桶的维护开销大，空间浪费
常见选择：
bucket_count = n（与元素数量相同）bucket_count = sqrt(n)（平衡时间和空间）bucket_count = n / 5（经验值）