算法概述
桶排序（Bucket Sort）是一种分布式排序算法，由E. J. Isaac和R. C. Singleton于1956年提出。它的工作原理是：
- 分桶：将待排序数组划分为若干个”桶”
- 分配：将每个元素根据其值分配到对应的桶中
- 局部排序：对每个非空桶内部进行排序（通常使用插入排序或快速排序）
- 合并：按顺序遍历所有桶，将元素依次取出
当输入数据均匀分布时，每个桶内的元素数量大致相同，此时桶排序的平均时间复杂度为O(n)。
核心思想
假设数据均匀分布在区间[min, max]内，将其划分为k个等宽区间（桶）。对于元素x，其所属桶的索引为：
bucketIndex = (x - min) * k / (max - min + 1)
Java完整实现
import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;
import java.util.List;
/**
* 桶排序完整Java实现
* 包含基础版本、自适应桶数版本、链表优化版本
*/
public class BucketSort {
/**
* 标准桶排序实现
* 时间复杂度：平均O(n + n²/k + k)，最坏O(n²)
* 空间复杂度：O(n + k)
* @param arr 待排序数组
* @param bucketCount 桶的数量
*/
public static void sort(double[] arr, int bucketCount) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// 找到最小值和最大值
double min = arr[0], max = arr[0];
for (double num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
// 处理所有元素相同的情况
if (min == max) return;
// 创建桶：使用ArrayList数组
@SuppressWarnings("unchecked")
List<Double>[] buckets = new ArrayList[bucketCount];
for (int i = 0; i < bucketCount; i++) {
buckets[i] = new ArrayList<>();
}
// 将元素分配到桶中
double range = max - min;
for (double num : arr) {
int bucketIndex = (int) ((num - min) / range * (bucketCount - 1));
buckets[bucketIndex].add(num);
}
// 对每个桶进行排序并合并
int index = 0;
for (List<Double> bucket : buckets) {
// 桶内使用Collections.sort（基于Timsort，稳定排序）
Collections.sort(bucket);
for (double num : bucket) {
arr[index++] = num;
}
}
}
/**
* 自动计算最优桶数量
* 通常桶数等于元素个数的平方根效果较好
*/
public static void sort(double[] arr) {
if (arr == null || arr.length <= 1) return;
int bucketCount = Math.max(1, (int) Math.sqrt(arr.length));
sort(arr, bucketCount);
}
/**
* 整数版本的桶排序
*/
public static void sortInt(int[] arr, int bucketCount) {
if (arr == null || arr.length <= 1) return;
int min = arr[0], max = arr[0];
for (int num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
if (min == max) return;
@SuppressWarnings("unchecked")
List<Integer>[] buckets = new ArrayList[bucketCount];
for (int i = 0; i < bucketCount; i++) {
buckets[i] = new ArrayList<>();
}
double range = max - min;
for (int num : arr) {
int bucketIndex = (int) ((num - min) / range * (bucketCount - 1));
buckets[bucketIndex].add(num);
}
int index = 0;
for (List<Integer> bucket : buckets) {
Collections.sort(bucket);
for (int num : bucket) {
arr[index++] = num;
}
}
}
/**
* 优化版本：使用插入排序处理小桶，减少递归开销
*/
public static void sortOptimized(double[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
double min = arr[0], max = arr[0];
for (double num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
if (min == max) return;
int bucketCount = Math.max(1, n / 10); // 每个桶平均10个元素
@SuppressWarnings("unchecked")
List<Double>[] buckets = new ArrayList[bucketCount];
for (int i = 0; i < bucketCount; i++) {
buckets[i] = new ArrayList<>();
}
double range = max - min;
for (double num : arr) {
int bucketIndex = (int) ((num - min) / range * (bucketCount - 1));
buckets[bucketIndex].add(num);
}
int index = 0;
for (List<Double> bucket : buckets) {
// 小桶使用插入排序，大桶使用快速排序
if (bucket.size() <= 20) {
insertionSort(bucket);
} else {
Collections.sort(bucket);
}
for (double num : bucket) {
arr[index++] = num;
}
}
}
/**
* 对List进行插入排序
*/
private static void insertionSort(List<Double> list) {
for (int i = 1; i < list.size(); i++) {
double key = list.get(i);
int j = i - 1;
while (j >= 0 && list.get(j) > key) {
list.set(j + 1, list.get(j));
j--;
}
list.set(j + 1, key);
}
}
/**
* 处理非均匀分布数据的增强桶排序
* 使用动态桶大小策略
*/
public static void sortAdaptive(double[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
double min = arr[0], max = arr[0];
for (double num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
if (min == max) return;
// 使用更多桶以提高均匀分布数据的性能
int bucketCount = n;
@SuppressWarnings("unchecked")
List<Double>[] buckets = new ArrayList[bucketCount];
for (int i = 0; i < bucketCount; i++) {
buckets[i] = new ArrayList<>();
}
double range = max - min;
for (double num : arr) {
// 使用更精细的分桶
int bucketIndex = Math.min(
(int) ((num - min) / range * bucketCount),
bucketCount - 1
);
buckets[bucketIndex].add(num);
}
int index = 0;
for (List<Double> bucket : buckets) {
if (bucket.size() > 1) {
Collections.sort(bucket);
}
for (double num : bucket) {
arr[index++] = num;
}
}
}
/**
* 验证排序正确性
*/
public static boolean isSorted(double[] arr) {
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) return false;
}
return true;
}
/**
* 打印桶分布情况（调试用）
*/
public static void printBucketDistribution(double[] arr, int bucketCount) {
double min = arr[0], max = arr[0];
for (double num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
int[] bucketSizes = new int[bucketCount];
double range = max - min;
for (double num : arr) {
int idx = (int) ((num - min) / range * (bucketCount - 1));
bucketSizes[idx]++;
}
System.out.println("桶分布情况（" + bucketCount + "个桶）：");
for (int i = 0; i < bucketCount; i++) {
double lower = min + range * i / bucketCount;
double upper = min + range * (i + 1) / bucketCount;
System.out.printf("桶%d [%.2f, %.2f): %d个元素%n", i, lower, upper, bucketSizes[i]);
}
}
/**
* 生成均匀分布的测试数据
*/
public static double[] generateUniformData(int size, double min, double max) {
double[] arr = new double[size];
for (int i = 0; i < size; i++) {
arr[i] = min + Math.random() * (max - min);
}
return arr;
}
/**
* 性能测试
*/
public static void performanceTest() {
int[] sizes = {1000, 10000, 100000};
System.out.println("桶排序性能测试（均匀分布数据）：");
System.out.println("规模 桶排序(ms) Arrays.sort(ms)");
for (int size : sizes) {
double[] arr1 = generateUniformData(size, 0, 1000);
double[] arr2 = arr1.clone();
long start1 = System.currentTimeMillis();
sort(arr1);
long time1 = System.currentTimeMillis() - start1;
long start2 = System.currentTimeMillis();
Arrays.sort(arr2);
long time2 = System.currentTimeMillis() - start2;
System.out.println(size + " " + time1 + " " + time2);
}
}
public static void main(String[] args) {
// 测试基本排序
double[] arr = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
System.out.println("原始数组：" + Arrays.toString(arr));
sort(arr, 5);
System.out.println("排序结果：" + Arrays.toString(arr));
System.out.println("是否正确排序：" + isSorted(arr));
System.out.println();
// 测试整数版本
int[] intArr = {54, 32, 67, 89, 12, 45, 78, 23};
System.out.println("整数原始数组：" + Arrays.toString(intArr));
sortInt(intArr, 4);
System.out.println("整数排序结果：" + Arrays.toString(intArr));
System.out.println();
// 测试均匀分布数据
double[] uniform = generateUniformData(20, 0, 100);
System.out.println("均匀分布原始数据：" + Arrays.toString(uniform));
printBucketDistribution(uniform, 5);
sort(uniform, 5);
System.out.println("排序结果：" + Arrays.toString(uniform));
System.out.println();
// 性能测试
performanceTest();
}
}
分桶策略详解
桶数量的选择
桶数量k的选择直接影响性能：
- k太小：每个桶内元素过多，局部排序开销增大
- k太大：空桶增多，空间浪费严重
- 经验值：通常取 k ≈ √n 或 k = n/10
均匀分布的假设
桶排序的最佳性能依赖于数据均匀分布的假设。当数据不均匀时（如大量数据集中在某个区间），某些桶会过载，导致性能退化到O(n²)。
非均匀数据的处理
- 自适应桶大小：根据数据密度动态调整桶的边界
- 更多桶：增加桶数量以降低每个桶的负载
- 递归桶排序：对过载的桶递归应用桶排序
复杂度分析
| 情况 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 最好情况 | O(n + k) | O(n + k) | 数据均匀分布，每个桶元素数量相近 |
| 平均情况 | O(n + n²/k + k) | O(n + k) | 当k≈√n时，平均为O(n) |
| 最坏情况 | O(n²) | O(n + k) | 所有元素落入同一个桶 |
与计数排序、基数排序的对比
| 特性 | 计数排序 | 桶排序 | 基数排序 |
|---|---|---|---|
| 数据类型 | 整数 | 浮点数/整数 | 整数/字符串 |
| 范围要求 | 有限范围 | 无严格要求 | 按位处理 |
| 稳定性 | 稳定 | 依赖桶内排序 | 稳定 |
| 最好时间 | O(n+k) | O(n+k) | O(d×(n+k)) |
| 额外空间 | O(n+k) | O(n+k) | O(n+k) |
| 分布要求 | 无 | 均匀分布最优 | 无 |
应用场景
- 浮点数排序：计数排序难以处理浮点数，桶排序天然支持
- 外部排序：数据量超过内存时，可将每个桶写入文件分别排序
- 数据分布分析：分桶过程本身可以揭示数据的分布特征
- 直方图计算：统计每个桶的元素数量即可得到数据分布直方图
总结
桶排序是一种优雅的分治排序策略，通过合理的分桶将全局排序问题分解为多个局部排序问题。在数据均匀分布的理想情况下，它能达到线性时间复杂度。理解桶排序有助于掌握分布式计算和并行排序的核心思想。
