桶排序

桶排序原理是将数组分到有限数量的桶子里，每个桶子再分别排序。假设现在有一组数字数量m个，大小从1到n，那么我们可以创建n个带编号的桶（编号从1到n），依次把数字按大小放入对应编号的桶中，接着按编号从小到大从桶中取出对应的数字，这时候数字自然就有序了。

描述：

前提：数据在某区间均匀分布，这里桶采用数组加链表的方式存储数据
1、先创建固定大小的桶，大小根据数据分布的区间决定，例如数据分布在0~9区间，就创建长度为10的数组；
2、将数据按大小放入对应编号的桶内，重复数据就往链表后面插（这里举例的数据0~9，桶的编号也刚好对应0-9）；
3、最后把桶内数据依次倒出。

代码：

    /**
     * 桶采用数组加链表的方式存储数据
     * @param array 目标数组
     * @param num 需要桶的个数
     */
    private void BucketSort(int[] array, int num) {
        LinkedList<Integer>[] bucket = new LinkedList[num];
        for (int data : array) {
            if (bucket[data] != null) {
                bucket[data].add(data);
            } else {
                LinkedList<Integer> list = new LinkedList<>();
                list.add(data);
                bucket[data] = list;
            }
        }
        int arrayIndex = 0;
        for (LinkedList<Integer> list: bucket) {
            while (list != null && list.size() > 0) {
                // 表里有值就拿出来
                array[arrayIndex++] = list.pop();
            }
        }
    }

测试代码：

    public void test() {
        int[] array = new int[]{5, 3, 7, 0, 1, 8 , 0, 0, 6, 2, 4, 6, 9};
        BucketSort(array, 10);
        for (int data : array) {
            System.out.print(data + " ");
        }
    }

运行结果：

0 0 0 1 2 3 4 5 6 6 7 8 9