桶排序是一种稳定的排序算法，它的原理是将要排序的数据分到几个有序的桶中，每个桶内的数据再单独进行排序。将每个桶的排序结果依次取出，组成有序序列。
桶排序适用于数据量比较大，且每个数据的取值范围不大的场景，比如：
public static void bucketSort(int[] arr, int bucketSize) {
if (arr.length == 0) {
return;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
// 桶的数量
int bucketCount = (maxValue - minValue) / bucketSize + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函数将数据分配到各个桶中
for (int i = 0; i < arr.length; i++) {
int index = (arr[i] - minValue) / bucketSize;
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int k = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 对每个桶进行排序，这里使用了快速排序
quickSort(bucket, 0, bucket.length - 1);
for (int value : bucket) {
arr[k++] = value;
}
}
}
// 自动扩容，并保存数据
private static int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
本文链接：http://task.lmcjl.com/news/8378.html