桶排序

参考链接：
https://www.geeksforgeeks.org/bucket-sort-2/
https://www.runoob.com/w3cnote/bucket-sort.html

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法（一般是使用插入排序算法）对于性能的影响至关重要。

1. 什么时候最快
   当输入的数据可以均匀的分配到每一个桶中。

2. 什么时候最慢
   当输入的数据被分配到了同一个桶中。

3. 示意图
   元素分布在桶中：

   
   image.png

整体步骤如下：
1.创建n个空桶
2.对每个数组元素执行相应操作：将nums[i]插入到桶[n * nums[i]]（这里num的数据集为0到1的浮点数，因此采用这种映射的方式）
3.使用插入排序对各个桶内元素进行排序
4.连接所有排序的桶

时间复杂度：
步骤1，2，4都花费O（n）的时间复杂度，主要分析是在第三步，如果所有数字均匀分布，则该步骤平均花费O（n）时间（详细证明见算法导论），因此整体的时间复杂度就是O（n）

代码实现：

   public static void bucketSort(double[] nums, int n) {
        ArrayList<ArrayList<Double>> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < list.size(); i++) {
            // 将nums[i]映射到桶中的第（n * nums[i]）个元素，这样最后收集的时候直接从小到大收集就可以了
            int index = (int) (nums[i] * n);
            list.get(index).add(nums[i]);
        }
        for (int i = 0; i < list.size(); i++) {
            Collections.sort(list.get(i));
        }

        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < list.get(i).size(); j++) {
                nums[index++] = list.get(i).get(j);
            }
        }
    }

    public static void main(String[] args) {
        double[] nums = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
        bucketSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }