什么是桶排序
摘自漫画算法：
桶排序是一种线性时间的排序算法。类似于计数排序所创建的统计数组，桶排序需要创建若干个桶来协助排序。
那么，桶排序中所谓的“桶”，有是什么呢？
假设有一个非整数数列如下：
4.5，0.84，3.25，2.18，0.5
让我们来看看桶排序的工作原理：
桶排序的第1步，就是创建这些桶，并确定每一个桶的区间范围。
具体需要建立多少个桶，如何确定桶的区间范围，有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外，前面各个桶的区间按照比例来确定。
区间跨度 = （最大值 - 最小值）/ （桶的数量 - 1）
第2步，遍历原始数列，把元素对号入座放入各个桶中。
第3步，对每个桶内部的元素分别进行排序（显然，只有第1个桶需要排序）。
第4步，遍历所有的桶，输出所有元素。
到此为止，排序结束。
桶排序的实现
整体代码
import java.util.*;
/**
* 描述：桶排序的实现。
* <p>
* Create By ZhangBiao
* 2020/6/2
*/
public class BucketSort {
public static double[] bucketSort(double[] arr) {
// 1、得到数列的最大值和最小值，并算出差值d
double max = arr[0];
double min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
double d = max - min;
// 2、初始化桶
int bucketNum = arr.length;
ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketList.add(new LinkedList<Double>());
}
// 3、遍历原始数组，将每个元素放入桶中
for (int i = 0; i < arr.length; i++) {
int num = (int) ((arr[i] - min) * (bucketNum - 1) / d);
bucketList.get(num).add(arr[i]);
}
// 4、对每个桶内部进行排序
for (int i = 0; i < bucketList.size(); i++) {
// JDK底层采用了归并排序或归并的优化版本
Collections.sort(bucketList.get(i));
}
// 5、输出全部元素
double[] sortedArray = new double[arr.length];
int index = 0;
for (LinkedList<Double> list : bucketList) {
for (double element : list) {
sortedArray[index] = element;
index++;
}
}
return sortedArray;
}
public static void main(String[] args) {
double[] arr = new double[]{4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09};
double[] sortedArray = bucketSort(arr);
System.out.println(Arrays.toString(sortedArray));
}
}
在上述代码中，所有的桶都保存在ArrayList集合中，每一个桶都被定义成一个链表，这样便于在尾部插入元素。
同时，上述代码使用了JDK的集合工具类Collections.sort来为桶内部的元素进行排序。Collections.sort底层采用的是归并排序或Timsort，各位读者可以简单地把它们当作一种时间复杂度为O(nlogn)的排序。
时间复杂度分析
假设原始数列有n个元素，分成n个桶。下面逐步来分析一下算法复杂度：
第1步，求数列最大值与最小值，运算量为n。
第2步，创建空桶，运算量为n。
第3步，把原始数列的元素分配到各个桶中，运算量为n。
第4步，在每个桶内部做排序，在元素分布相对均匀的情况下，所有桶的运算量之和为n。
第5步，输出排序数列，运算量为n。
因此，桶排序的总体时间复杂度为O(n)。
至于空间复杂度就很容易得到了，同样是O(n)。
桶排序的性能并非绝对稳定。如果元素的分布极不均衡，在极端情况下，第一个桶中有n-1个元素，最后一个桶中有1个元素。此时的时间复杂度将退化为O(nlogn)，而且还白白创建了许多空桶。
由此可见，并没有绝对好的算法，也没有绝对不好的算法，关键要看具体的场景。
