桶排序

什么是桶排序
桶排序是计数排序的衍化
桶排序需要创建若干个桶来装元素协助排序。
每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。
假设有一个非整数数列如下：
4.5，0.84，3.25，2.18，0.5
让我们来看看桶排序的工作原理。
桶排序的第1步，就是创建这些桶，并确定每一个桶的区间范围。

image.png
具体需要建立多少个桶，如何确定桶的区间范围，有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外，前面各个桶的区间按照比例来确定。
区间跨度 = （最大值-最小值）/ （桶的数量 - 1）
第2步，遍历原始数列，把元素对号入座放入各个桶中。
image.png
第3步，对每个桶内部的元素分别进行排序（显然，只有第1个桶需要排序）。
image.png
第4步，遍历所有的桶，输出所有元素。
0.5，0.84，2.18，3.25，4.5
到此为止，排序结束。

具体代码：

public static double[] bucketSort(double[] array){
    //1.得到数列的最大值和最小值，并算出差值d
    double max = array[0];
    double min = array[0];
    for(int i=1; i<array.length; i++) {
        if(array[i] > max) {
            max = array[i];
        }
        if(array[i] < min) {
            min = array[i];
        }
    }
    double d = max - min;

    //2.初始化桶
    int bucketNum = array.length;
    ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketList.add(new LinkedList<Double>());
    }

    //3.遍历原始数组，将每个元素放入桶中
    for(int i = 0; i < array.length; i++){
        int num = (int)((array[i] - min) * (bucketNum-1) / d);
        bucketList.get(num).add(array[i]);
    }

    //4.对每个桶内部进行排序
    for(int i = 0; i < bucketList.size(); i++){
        //JDK 底层采用了归并排序或归并的优化版本
        Collections.sort(bucketList.get(i));
    }

    //5.输出全部元素
    double[] sortedArray = new double[array.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[] 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));
}