思路
桶排序的思想同归并排序一样，也是基于分治法来加快排序的速度的。主要思想就是把整个数组按范围放到不同的桶中，各个桶各自进行排序，每个桶都排好序之后，整个数组的排序也就完成了。
思路：
1、确定桶的个数和每个桶的范围；
2、将数组分配到桶中；
3、桶内进行排序（可以继续使用桶排序，但一般会采用其他排序算法）；
4、从桶中取出排好序的数。
讲解
有数组如下：
image.png
加入分配5个桶，分别是[1, 20)、[20, 40)、[40，60)、[60，80)、[80，99)：
image.png
然后给数字进行入桶：
image.png
将桶中的数字进行排序：
image.png
将数字从桶中取出来即可：
image.png
实现
@Test
public void sortTest() {
int[] nums = new int[]{2, 1, 31, 15, 28, 88, 46, 55, 57, 98};
bucketSort(nums);
System.out.println(Arrays.toString(nums));
}
private void bucketSort(int[] nums) {
if (nums.length < 2) {
return;
}
// 找出最大值和最小值，决定分配几个桶
int maxValue = nums[0];
int minValue = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > maxValue) {
maxValue = nums[i];
}
if (nums[i] < minValue) {
minValue = nums[i];
}
}
// 桶个数
int bucketCount = (maxValue - minValue) / (nums.length * 2) + 1;
// 如果桶个数小于两个，就没有必要分桶，直接排序即可
if (bucketCount < 2) {
Arrays.sort(nums);
return;
}
// 桶间隔
int gap = (maxValue + 1) / (bucketCount - 1);
// 声明桶
int[][] bucketArray = new int[bucketCount][0];
// 遍历入桶
for (int i = 0; i < nums.length; i++) {
bucketArray[nums[i] / gap] = arrayAppend(bucketArray[nums[i] / gap], nums[i]);
}
// 桶内排序和取出
int index = 0;
for (int i = 0; i < bucketCount; i++) {
// 每一个桶内进行排序，这里就简写了
Arrays.sort(bucketArray[i]);
// 取出放到结果数组
for (int j = 0; j < bucketArray[i].length; j++) {
nums[index++] = bucketArray[i][j];
}
}
}
private int[] arrayAppend(int[] array, int num) {
int[] ints = Arrays.copyOf(array, array.length + 1);
ints[ints.length - 1] = num;
return ints;
}
看下运行结果：
image.png
