桶排序（Bucket Sort）是一种分布式排序算法，它主要利用元素的分布特征，通过将待排序的数据分配到几个有序的桶（bucket）中，然后对每个桶内的数据单独排序（每个桶可以使用不同的排序算法，甚至也可以递归地再次使用桶排序），最后按照顺序依次取出每个桶中的元素，组合起来即可得到整体有序的数据。
以下是桶排序的主要步骤：
初始化： 根据待排序数据的范围和分布特性确定桶的数量和每个桶的容量（范围）。一般来说，每个桶代表一个连续的数值区间。
分配： 遍历输入数据，将每个元素放入相应的桶中。分配依据预先设计好的映射规则，通常是将数据除以桶的数量向下取整，以便将相近的数据放入同一个桶内。
排序桶内数据： 对每个非空的桶，使用一种适合的排序算法进行排序。如果数据足够均匀且桶足够多，有时候桶内的数据本身就可能是有序的。
收集结果： 从头到尾依次遍历每个桶，按照桶的顺序将桶内的数据依次取出并连接起来，最终得到的就是排序好的序列。
Java实现桶排序的一个简化示例：
import java.util.*;
public class BucketSort {
public static void bucketSort(int[] arr, int bucketSize) {
if (arr == null || arr.length == 0)
return;
// 获取数组中的最大值和最小值，确定桶的范围
int minValue = Arrays.stream(arr).min().getAsInt();
int maxValue = Arrays.stream(arr).max().getAsInt();
// 计算桶的数量
int bucketCount = (maxValue - minValue) / bucketSize + 1;
List<List<Integer>> buckets = new ArrayList<>(bucketCount);
// 初始化桶
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<>());
}
// 分配元素到各自的桶中
for (int num : arr) {
int bucketIndex = (num - minValue) / bucketSize;
buckets.get(bucketIndex).add(num);
}
// 对每个桶进行排序（这里使用Collections.sort()对List进行排序）
for (List<Integer> bucket : buckets) {
Collections.sort(bucket);
}
// 从各个桶中收集排序好的元素
int index = 0;
for (List<Integer> bucket : buckets) {
for (Integer value : bucket) {
arr[index++] = value;
}
}
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 1, 9, 2, 7, 4, 6};
bucketSort(arr, 3);
System.out.println(Arrays.toString(arr));
}
}注意：桶排序效率的关键在于如何有效地分配元素到桶内以及桶内排序的算法选择。当输入数据均匀分布并且桶数量适当时，桶排序可以达到线性时间复杂度O(n+k)，其中k是桶的数量。但若数据分布非常不均匀或者桶内排序成本很高，则桶排序的效率会下降。
原文链接: https://www.yukx.com/arithmetic/article/details/2474.html 优科学习网桶排序算法
