1. 简介
本文将深入探讨 桶排序（Bucket Sort）算法。我们会先简要介绍其核心思想，然后一步步实现 Java 版本的桶排序，并辅以单元测试验证正确性。最后，还会分析该算法的时间复杂度。
对于有经验的开发者来说，排序算法并不陌生，但桶排序因其独特的分治思想，在特定场景下表现优异——尤其是在数据分布较均匀时，能实现接近线性的排序速度，是一种值得掌握的“非比较型”排序技巧。
2. 桶排序的原理
桶排序（也叫箱排序）是一种基于分桶思想的排序算法。它的核心思路是：
✅ 将待排序元素分配到多个“桶”中
✅ 对每个桶内部单独排序
✅ 最后按顺序合并所有桶
这样做的好处是：减少了元素之间的直接比较次数，从而在理想情况下显著提升性能。
执行桶排序通常包含以下四个步骤：
- 创建若干个初始为空的桶（即容器）
- 根据某种规则，将原数组中的元素映射到对应的桶中
- 对每个非空桶内的元素进行排序（可用任意排序算法）
- 按照桶的顺序，依次将所有元素重新合并成一个有序序列
⚠️ 注意：桶的数量和映射函数的设计非常关键，直接影响性能甚至正确性。
3. Java 实现
虽然桶排序不依赖特定语言，但我们这里用 Java 来实现整数列表的排序。下面逐段拆解代码逻辑。
3.1 桶的初始化
首先需要一个哈希函数（hash function），用来决定某个元素应该放入哪个桶。这个函数要尽可能让数据均匀分布。
private int hash(int i, int max, int numberOfBuckets) {
return (int) ((double) i / max * (numberOfBuckets - 1));
}
📌 解释：
i是当前元素值max是整个输入列表的最大值numberOfBuckets是桶总数- 通过归一化
(i / max)再乘以(桶数 - 1)，得到一个[0, 桶数-1]范围内的索引
接着，我们通常选择桶的数量为输入数据量的平方根，这是一个经验性策略，简单粗暴且效果不错：
final int numberOfBuckets = (int) Math.sqrt(initialList.size());
List<List<Integer>> buckets = new ArrayList<>(numberOfBuckets);
for(int i = 0; i < numberOfBuckets; i++) {
buckets.add(new ArrayList<>());
}
然后还需要一个辅助方法来找出最大值，用于哈希计算：
private int findMax(List<Integer> input) {
int m = Integer.MIN_VALUE;
for (int i : input) {
m = Math.max(i, m);
}
return m;
}
3.2 元素分发
有了桶和哈希函数后，就可以把原始数据逐个分配进对应桶中：
int max = findMax(initialList);
for (int i : initialList) {
buckets.get(hash(i, max, numberOfBuckets)).add(i);
}
✅ 这一步时间复杂度是 O(n)，每个元素只访问一次。
3.3 单个桶排序
每个桶内部使用 Java 自带的 List.sort() 配合自然序比较器排序：
Comparator<Integer> comparator = Comparator.naturalOrder();
for(List<Integer> bucket : buckets){
bucket.sort(comparator);
}
📌 实际上，如果桶内元素少，可以直接用插入排序；多的话 JDK 会自动优化为 TimSort。
3.4 合并结果
最后，把所有桶按顺序拼接起来即可：
List<Integer> sortedArray = new LinkedList<>();
for(List<Integer> bucket : buckets) {
sortedArray.addAll(bucket);
}
return sortedArray;
✅ 使用 LinkedList 是为了频繁添加操作更高效，当然 ArrayList 预估好容量也没问题。
4. 测试代码
写完实现，必须来个单元测试验证一下是否靠谱：
BucketSorter sorter = new IntegerBucketSorter();
List<Integer> unsorted = Arrays.asList(80,50,60,30,20,10,70,0,40,500,600,602,200,15);
List<Integer> expected = Arrays.asList(0,10,15,20,30,40,50,60,70,80,200,500,600,602);
List<Integer> sorted = sorter.sort(unsorted);
assertEquals(expected, sorted);
✅ 测试用例覆盖了零、正数、重复值（如50）、大数等常见情况，结果符合预期。
5. 时间复杂度分析
桶排序的性能高度依赖数据分布，不能一概而论。
5.1 最坏情况 ❌
当所有元素都被分到同一个桶里时（比如数据极不均匀），那就退化成对整个数组做一次普通排序。
假设我们用的是 O(n log n) 的排序算法（如归并排序），那整体复杂度就是：
O(n + n log n) = O(n log n)
但如果桶内用了插入排序，最坏情况下是 O(n²)，那么总时间就是：
O(n²)
⚠️ 踩坑提醒：设计哈希函数时一定要避免大量元素集中在一个桶！
5.2 平均情况 ✅
理想状态下，元素均匀分布在各个桶中，每个桶只有常数个元素（比如 k 个），那么：
- 分配元素：O(n)
- 排序每个桶：共 n/k 个桶，每桶排序 O(k²) 或 O(k log k)，总时间 ≈ O(n)
- 合并桶：O(n)
所以整体时间复杂度为：
O(n)
🎉 这就是桶排序的魅力所在——在线性时间内完成排序，远超快排、归并等比较排序的 O(n log n) 下限。
6. 总结
本文实现了 Java 版本的桶排序，展示了如何通过“分而治之”的思想优化排序过程。关键点总结如下：
- ✅ 桶的数量建议设为 √n，平衡空间与性能
- ✅ 哈希函数设计要保证数据尽量均匀分布
- ✅ 桶内排序可复用 JDK 提供的高效排序
- ✅ 理想情况下时间复杂度可达 O(n)，但最坏情况可能退化到 O(n²)
桶排序适用于浮点数、整数且分布较均匀的场景，比如成绩排序、评分系统等。但在实际项目中需谨慎评估数据特征，否则容易“踩坑”。
示例代码已托管至 GitHub：https://github.com/dev-example/bucket-sort-demo