桶排序

————————————

桶排序

让我们先来回顾一下计数排序：

计数排序需要根据原始数列的取值范围，创建一个统计数组，用来统计原始数列中每一个可能的整数值所出现的次数。

原始数列中的元素（整数），和统计数组的下标是一一对应的，以数列的最小值作为偏移量。比如原始数列的最小值是90，那么整数95对应的统计数组下标就是 95-90 = 5。

桶排序

那么，桶排序当中所谓的“桶”，又是什么概念呢？

每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。桶排序的第一步，就是创建这些桶，确定每一个桶的区间范围：

桶排序

具体建立多少个桶，如何确定桶的区间范围，有很多不同的方式。

我们这里创建的桶数量等于原始数列的元素数量，除了最后一个桶只包含数列最大值，前面各个桶的区间范围按照比例确定。

区间跨度（大小） = （最大值-最小值）/ （桶的数量 - 1）

涛声依旧注：除了最后一个桶之外，其余的桶均分最大值和最小值的差值，区间跨度（大小）也就是桶的范围的大小。

第二步，遍历原始数列，把元素对号入座放入各个桶中：

桶排序

第三步，每个桶内部的元素分别排序（显然，只有第一个桶需要排序）：

桶排序

第四步，遍历所有的桶，输出所有元素：

0.5，0.84，2.18，3.25，4.5

到此为止，排序结束。

桶排序


    public static void bucketSort(double[] nums) {
        double max = nums[0];
        double min = nums[0];
        for (double num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        double diff = max - min;

        int bucketCount = nums.length;
        List<Double>[] buckets = new ArrayList[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }

        for (int i = 0; i < nums.length; i++) {
            int bucketIndex = (int) ((nums[i] - min) / diff * ((bucketCount - 1)));
            buckets[bucketIndex].add(nums[i]);
        }

        for (int bucketIndex = 0; bucketIndex < bucketCount; bucketIndex++) {
            Collections.sort(buckets[bucketIndex]);
        }

        int index = 0;
        for (int bucketIndex = 0; bucketIndex < bucketCount; bucketIndex++) {
            for (int numIndex = 0; numIndex < buckets[bucketIndex].size(); numIndex++) {
                nums[index++] = buckets[bucketIndex].get(numIndex);
            }
        }
    }

public static void main(String[] args) {
    double[] array = new double[] {4.12,6.421,0.0023,3.0,2.123,8.122,4.12, 10.09};
    double[] sortedArray = bucketSort(array);
    System.out.println(Arrays.toString(sortedArray));
}

代码中，所有的桶保存在ArrayList集合当中，每一个桶被定义成一个链表（LinkedList），这样便于在尾部插入元素。

定位元素属于第几个桶，是按照比例来定位：

(array[i] - min) * (bucketNum-1) / d

涛声依旧注：要定位元素 array[i] 在第几个桶，先减去最小值min,看它在桶数组（ArrayList）中的偏移为多少，然后除以桶的区间大小d/(buketNum-1),相当于乘以(buketNum-1)/d，除以桶区间大小就可以定位是在哪个桶里了。

同时，代码使用了JDK的集合工具类Collections.sort来为桶内部的元素进行排序。Collections.sort底层采用的是归并排序或Timsort，小伙伴们可以简单地把它们当做是一种时间复杂度 O（nlogn）的排序。

桶排序