目录

桶排序

基本介绍

一句话总结:划分多个范围相同的区间,每个子区间自排序,最后合并。 桶排序是计数排序的扩展版本,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过映射函数,将待排序数组中的元素映射到各个对应的桶中,对每个桶中的元素进行排序,最后将非空桶中的元素逐个放入原序列中。 桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效。

图解过程

https://gitee.com/lienhui68/picStore/raw/master/null/20200624190954.png

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
    /**
     * 桶排序
     *
     * @param arr
     */
    public static void bucketSort(int[] arr) {
        // 1. 计算最小值和最大值
        int min = arr[0], max = arr[0];
        for (int i : arr) {
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        // 2. 确定桶的数量
        int num = (max - min) / arr.length + 1;
        List<List<Integer>> buckets = Lists.newArrayList();
        for (int i = 0; i < num; i++) {
            buckets.add(Lists.newArrayList());
        }
        // 3. 将元素放入对应桶中
        for (int i : arr) {
            int index = (i - min) / arr.length;
            buckets.get(index).add(i);
        }
        // 4. 对每个桶进行排序
        for (int i = 0; i < buckets.size(); i++) {
            // 这里自行选择排序算法
            Collections.sort(buckets.get(i));
        }
        // 5. 将桶中的元素放到原序列
        int index = 0;
        for (int i = 0; i < buckets.size(); i++) {
            for (int j = 0; j < buckets.get(i).size(); j++) {
                arr[index++] = buckets.get(i).get(j);
            }
        }
    }

参考

【排序】图解桶排序