桶排序算法
桶排序（Bucket Sort）是一种分布式排序算法，它的核心思想是：把数据分到若干个有序的“桶”里，每个桶内部再进行排序（比如插入排序或快速排序），最后把所有桶的数据按顺序合并起来。
1. 基本原理（通俗理解）
假设要对[0, 1)范围的小数排序：
创建
k个桶，第 i 个桶负责存放区间[i/k, (i+1)/k)的元素。遍历数组，根据元素值把它放到对应的桶里。
对每个非空桶内部进行排序（通常用插入排序）。
按桶的顺序，依次取出每个桶里的元素，完成排序。
2. 适用场景
元素分布相对均匀（比如随机小数）。
数据范围已知且易于分段。
可以容忍一定额外空间开销。
3. 时间 & 空间复杂度
平均时间复杂度：O(n+k)O(n+k)（理想情况下桶内元素很少）
最坏时间复杂度：O(n2)O(n2)（所有元素进同一个桶，且桶内用低效排序）
空间复杂度：O(n+k)O(n+k)，k 是桶的数量
关键在于：桶的数量和元素分布决定效率。
4. 简单例子（整数排序）
对[29, 25, 3, 49, 9, 37, 21, 43]用桶排序（假设范围 0~50，分 5 个桶，每桶容量 10）：
桶0（0~9）：3, 9
桶1（10~19）：无
桶2（20~29）：29, 25, 21
桶3（30~39）：37
桶4（40~49）：49, 43
桶内排序（插入排序）：
桶2：21, 25, 29
桶4：43, 49
按桶顺序合并：3, 9, 21, 25, 29, 37, 43, 49✅
5. 与常见排序对比
| 排序 | 平均复杂度 | 是否稳定 | 适用情况 |
|---|---|---|---|
| 桶排序 | O(n + k) | 稳定 | 数据分布均匀 |
| 计数排序 | O(n + k) | 稳定 | 整数且范围小 |
| 基数排序 | O(d(n+k)) | 稳定 | 整数或固定长度字符串 |
| 快速排序 | O(n log n) | 不稳定 | 通用 |
6. 一句话总结
桶排序 = 分桶 + 桶内排序 + 合并。适合数据均匀分布时的线性时间复杂度排序。
1. 通用桶排序模板（适用于数值） java import java.util.*; public class BucketSort { public static void bucketSort(double[] arr) { if (arr == null || arr.length <= 1) return; int n = arr.length; // 1. 创建 n 个桶 List<Double>[] buckets = new List[n]; for (int i = 0; i < n; i++) { buckets[i] = new ArrayList<>(); } // 2. 把元素放入对应的桶 for (double num : arr) { int idx = (int) (num * n); // 映射到 [0, n-1] (假设num范围[0,1)) buckets[idx].add(num); } // 3. 对每个桶内部排序 for (List<Double> bucket : buckets) { Collections.sort(bucket); // 这里用内置排序（TimSort） } // 4. 合并结果 int index = 0; for (List<Double> bucket : buckets) { for (double num : bucket) { arr[index++] = num; } } } // 测试 public static void main(String[] args) { double[] arr = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51}; bucketSort(arr); System.out.println(Arrays.toString(arr)); } } 2. 整数排序的桶排序（指定最大值和桶数） java public static void bucketSort(int[] arr, int maxVal) { if (arr == null || arr.length <= 1) return; // 创建桶数组（每个桶是一个 ArrayList） List<Integer>[] buckets = new List[maxVal + 1]; for (int i = 0; i <= maxVal; i++) { buckets[i] = new ArrayList<>(); } // 放入桶（数值就当作下标） for (int num : arr) { buckets[num].add(num); } // 合并 int index = 0; for (int i = 0; i <= maxVal; i++) { for (int num : buckets[i]) { arr[index++] = num; } } } 注意：如果整数范围很大但数量少，这种「每个值一个桶」会浪费空间，更合理的做法是分段桶，类似小数版。