參考：https://www.cnblogs.com/onepixel/articles/7674659.html

其他排序算法傳送門：https://blog.csdn.net/jkdcoach/article/details/87442482

源碼：https://github.com/sunrui849/sort

桶排序

桶排序是計數排序的更新版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的确定。桶排序 (Bucket sort)的工作的原理：假設輸入資料服從均勻分布，将資料分到有限數量的桶裡，每個桶再分别排序（有可能再使用别的排序算法或是以遞歸方式繼續使用桶排序進行排）。

1.1 算法描述

• 設定一個定量的數組當作空桶；
• 周遊輸入資料，并且把資料一個一個放到對應的桶裡去；
• 對每個不是空的桶進行排序；
• 從不是空的桶裡把排好序的資料拼接起來。 

1.2 圖檔示範

1.3特性

桶排序與計數排序差不多，相當于計數排序隻是每一個桶内隻存相同的值。分桶相當于一次排序，隻是單元是一個範圍。

1.4代碼實作

//設定桶的大小
    private static final int BUCKET_SIZE = 5;

    /**
     * 從小到大
     * 桶排序
     * @param arr
     * @return
     */
    public static int[] sort(int[] arr) {
        if (arr == null || arr.length == 0){
            return arr;
        }

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int value : arr) {
            max = Math.max(max,value);
            min = Math.min(min,value);
        }

        //桶的數量
        int bucketNum = (max - min)/BUCKET_SIZE + 1;
        //以ArrayList作為桶的容器，參數為設定桶的數量，即ArrayList預設的長度
        List<List<Integer>> bucket = new ArrayList<List<Integer>>(bucketNum);
        //初始化桶
        for (int i = 0; i < bucketNum; i++) {
            bucket.add(new ArrayList<Integer>());
        }

        //将資料放到桶裡
        for (int value : arr){
            int num = (value - min)/BUCKET_SIZE;
            bucket.get(num).add(value);
        }

        //排序每一個桶内的資料
        for (int i = 0; i < bucketNum; i++) {
            Collections.sort(bucket.get(i));
        }

        //更新數組内資料
        int index = 0;
        for (List<Integer> content : bucket){
            for (Integer value : content) {
                arr[index++] = value;
            }
        }
        return arr;
    }