入门算法：桶排序

上手难度：★★★

算法复杂度：O(N+C)，其中C=N*(logN-logM)

排序思想：

设置5个桶，先取到数组arr里的最大值和最小值，通过最大值和最小值的差值除以5得到每个桶的容量，再以这个容量值bucketCount 创建出二维数组，对应的就是形成了bucketCount个一维数组，再对数组arr里的值进行除5划分到bucketCount个一维数组中，再分别对这些一维数组进行排序，最后挨个遍历bucketCount索引对应的一维数组，填充新的值到arr中，自然就是排好序的结果

注意：不要理解成一个桶对应一个二维数组，而是每个一维数组的每个索引对应一类桶，在之前的计数排序里面，也是同样的索引放到同一个桶里

代码实现：

public class BucketSort {

    private static final InsertSort insertSort = new InsertSort();

    public static int[] sort(int[] sourceArray){
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return bucketSort(arr, 5);
    }

    private static int[] bucketSort(int[] arr, int bucketSize){
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        //遍历得到最小值和最大值
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        //本例中，这里的值是（50-2） / 5 + 1 = 10，确定每个桶的最大容量，通过最大值和最小值的差值就可以得到总共需要多少个空间用于存放
        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];
        //专门new一个二维数组，这个二维数组在本例中有10个一维数组，每个一维数组最多放5个元素，也就对应了桶的序号
        //不要理解成一个桶对应一个二维数组，而是每个一维数组的每个索引对应一类桶，在之前的计数排序里面，也是同样的索引放到同一个桶里

        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            //遍历arr里的值，通过/bucketSize这种方式，根据大小分配到桶里
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            //得到桶的索引后，将对应的arr值放到索引对应的一维数组中
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            //遍历这个buckets，得到每一个一维数组
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            bucket = insertSort.sort(bucket);
            // 然后循环遍历这个一维数组，将arr挨个接收已经排序好的值即可
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     * 将arr扩容一个值，并放置到最后一位，然后返回arr
     */
    private static int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

    public static void main(String[] args) {

        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        arr = sort(arr);

        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }

    }
}

特点：

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
例如每个桶就装一个值的做法，无需进行比较排序，但此时的空间消耗最大