排序(9) 桶排序

发表于 | 分类于 | 阅读次数:

假设有一组长度为N的待排关键字序列K[1….n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标i)，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。 然后依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列。

桶排序

思想

一个长度为20的doule类型数组，取值范围从0到10，要求用最快的速度把这20个double类型元素从小到大进行排序。
当数列取值范围过大，或者不是整数时，不能适用计数排序。到那时可以使用桶排序来解决问题。

桶排序同样是一种线性时间的排序算法，类似于计数排序所创建的统计数组，桶排序需要创若干个 桶来协助排序。

计数排序：
计数排序需要根据原始数列的取值范围，创建一个统计数组，用来统计原始数列中每一个可能的整数值所出现的次数。
原始数列中的整数值，和统计数组的下标是一一对应的，以数列的最小值作为偏移量，比如原始数列的最小值是90，那么整数对应的统计数组下标就是95-90=5。

桶排序当中的桶的概念：
每一个桶(bucket)代表一个区间范围，里面可以承载一个或多个元素。

桶排序的第一步，就是创建这些桶，确定每一个桶的区间范围。

4.5 0.84 3.25 2.18 0.5
[0.5, 1.5) [1.5, 2.5) [2.5, 3.5) [3.5, 4.5) [4.5, 4.5]

具体建立多少个桶，如何确定桶的区间范围，有很多不同的方式。
这里创建的桶数量等于原始数列的元素数量，除了最后一个桶只包含数列最大值，前面各个桶的区间按照比例确定。
区间跨度 = （最大值-最小值）/ （桶的数量 - 1）

第二步，遍历原始数列，把元素对号入座放入各个桶中：
0.84 0.5 2.18 3.25 4.5
[0.5, 1.5) [1.5, 2.5) [2.5, 3.5) [3.5, 4.5) [4.5, 4.5]

第三步，每个桶内部的元素分别排序（显然，只有第一个桶需要排序）：

第四步，遍历所有的桶，输出所有元素：
0.5， 0.84， 2.18， 3.25， 4.5

到此为止，排序结束。

桶排序代码实现

桶排序
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class BucketSort {
    public static double[] bucketSort(double[] arr) {
        // 1. 得到数列的最大值和最小值，并计算出差值d
        double max = arr[0];
        double min = arr[0];

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }

        double d = max - min;

        // 2. 初始化桶
        int bucketNum = arr.length;

        ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<Double>());
        }

        // 3. 遍历原始数组，将每个元素放入桶中
        for (int i = 0; i < arr.length; i++) {
            int num = (int) ((arr[i] - min) * (bucketNum - 1) / d);
            bucketList.get(num).add(arr[i]);
        }

        // 4. 对每个桶内部进行排序
        for (int i = 0; i < bucketList.size(); i++) {
            // JDK低层采用了归并排序或归并的优化版本
            Collections.sort(bucketList.get(i));
        }

        // 5. 输出全部元素
        double[] sortedArray = new double[arr.length];
        int index = 0;

        for (LinkedList<Double> list : bucketList) {
            for (double element : list) {
                sortedArray[index] = element;
                index++;
            }
        }
        return sortedArray;
    }

    public static void main(String[] args) {
        double[] arr = { 4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09 };
        double[] sortedArr = bucketSort(arr);

        System.out.println(Arrays.toString(sortedArr));
    }
}

代码中，所有的桶保存在ArrayList集合当中，每一个桶被定义成一个链表（LinkedList），这样便于在尾部插入元素。

定位元素属于第几个桶，是按照比例来定位：
(array[i] - min) * (bucketNum-1) / d

同时，代码使用了JDK的集合工具类Collections.sort来为桶内部的元素进行排序。Collections.sort底层采用的是归并排序或Timsort，小伙伴们可以简单地把它们当做是一种时间复杂度 O（nlogn）的排序。

基数排序

基数排序

基数排序也可以看作一种桶排序，不断的使用不同的标准对数据划分到桶中，最终实现有序。基数排序的思想是对数据选择多种基数，对每一种基数依次使用桶排序。

基数排序的步骤：以整数为例，将整数按十进制位划分，从低位到高位执行以下过程。

  1. 从个位开始，根据0~9的值将数据分到10个桶桶，例如12会划分到2号桶中。

  2. 将0~9的10个桶中的数据顺序放回到数组中。

重复上述过程，一直到最高位。

上述方法称为LSD（Least significant digital），还可以从高位到低位，称为MSD。

复杂度及稳定性

算法复杂度：
时间复杂度（平均）： O(n+m+n(logn-logm))
时间复杂度（最坏）： O(nlogn)
时间复杂度（最好）： O(n)

空间复杂度： O(m+n)
桶排序也是稳定的排序算法。

假设原始数列有n个元素，分成m个桶（我们采用分桶方式m=n），平均每个桶的元素个数为 n/m

下面逐步分析算法复杂度

第一步，求数列最大最小值，运算量为n。
第二步，创建空桶，运算量为m。
第三步，遍历原始数列，运算量为n。
第四步在每个桶内部做排序，由于使用了O(nlogn)的排序算法，所以运算量为 n/m · log(n/m ) · m。
第五步，输出排序数列，运算量为n。

加起来，总的运算量为3n+m+ n/m · log(n/m ) · m = 3n+m+n(logn-logm)
去掉系数，时间复杂度为：
O(n+m+n(logn-logm))
至于空间复杂度就很明显了：
空桶占用的空间 + 数列在桶中占用的空间 = O(m+n)

桶排序在性能上并非绝对稳定。理想情况下，桶中的元素均匀分布，当n=m时，时间复杂度可以达到O(n)；但是，如果桶内元素的分布极不均匀，极端情况下第一个桶中有n-1个元素，，最后一个桶中有1个元素。此时的时间复杂度将退化成为O(nlogn)，还白白创建了许多空桶。

0%