桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

算法步骤

1.根据待排序集合中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数（
f(x) = x / 10 -c
c= max / 10 - min / 10）；
2.遍历待排序集合，将每一个元素移动到对应的桶中；
3.对每一个桶中元素进行排序，并移动到已排序集合中。

动图演示

元素分布在桶中：

Bucket_sort_1.svg_.png

然后，元素在每个桶中排序：

Bucket_sort_2.svg_.png

复杂度

时间复杂度 = O(n+n(logn-logm)) 空间复杂度 = O(n+m)

代码实现

public static void bucketsort(int[] arr) {
        int len = arr.length,min = arr[0],max = arr[len - 1];

        for (int i:arr) {
            if (i < min) {
                min = i;
            } else if (i > max) {
                max = i;
            }
        }

        int bucketCount = (max - min) / 10 + 1;
        int[][] buckets = new int[bucketCount][0];

        for (int i = 0; i < len; i++) {
            int index = (arr[i] - min) / 10;
            buckets[index] = arrAppend(buckets[index],arr[i]);
        }

        int step = 0;
        for (int[] bocket: buckets) {

            if (bocket.length <= 0) {
                continue;
            }

            bocket = QuickSort.quick_sort2(bocket,0,bocket.length - 1);

            for (int value:bocket) {
                arr[step++] = value;
            }
        }
 }


    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
 private static int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
}