桶排序

本文内容和代码来源于《漫画算法》。 针对计数排序的局限性，桶排序做出了弥补，时间复杂度同样是线性级。类似于计数排序所创建的统计数组，桶排序需要创建若干个桶来协助排序。 那么桶排序中所谓的“桶”，又是什么呢？ 每一个桶(bucket)代表一个区间范围，里面可以承载一个或多个元素。 假设有一个非整数数列如下： 4.5,0.84,3.25,2.18,0.5 让我们来看看桶排序的工作原理。 桶排序的第一步，就是创建这些桶，并确定每一个桶的区间范围。 具体需要建立多少个桶，如何确定桶的区间范围，有很多种不同的方式，我们这里创建的桶数量等于原始数列的元素个数。除最后一个桶只包含数列最大值外，前面各个桶的区间，按照比例来确定。 区间跨度 = (最大值 - 最小值) / (桶的数量 - 1)

第2步，遍历原始数列，把元素对号入座放入各个桶中。 第3步，对每个桶内部的元素分别进行排序 第4步，遍历所有的桶，输出所有元素。 0.5, 0.84, 2.18, 3.25, 4.5 排序结束 java实现如下：

double[] bucketSort(double[] arr) { // 1.得到数列的最大值和最小值 double max = 0; double min = 0; for (int i = 0; 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[] sortedArr = new double[arr.length]; int index = 0; for (LinkedList<Double> list : bucketList) { for (double element : list) { sortedArr[index] = element; index++; } } return sortedArr; } @Test public void fun1() { double[] arr = new double[] { 4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09 }; double[] sortedArr = bucketSort(arr); System.out.println(Arrays.toString(sortedArr)); }

总结： 桶排序的时间复杂度：O(n)，空间复杂度O(n) 桶排序的性能并非绝对稳定。如果元素分布极不均衡，在极端情况下，第一个桶中有n-1个元素，最后一个桶中有1个元素。此时的时间复杂度将退化为O(nlogn)，而且还白白创建了许多空桶。

由此可见，没有绝对好的算法，也没有绝对不好的算法，关键要看具体的场景。