动画:一篇文章快速学会桶排序

内容介绍

桶排序简介

前面学过计数排序，计数排序是一个非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)。

所谓桶就是存放多个数据的容器，桶排序也是非基于比较的排序算法，将待排序数据按照一定的规则存放到对应的桶中，再进行排序与合并。桶排序可以对一定范围内的数据包括小数进行排序。桶排序可以突破基于比较排序算法的时间复杂度O(nlogn)。

桶排序的思想

将待排序数据分配到有限数量的桶里。每个桶再单独进行子排序，最后按顺序将多个桶中的数据进行合并，排序完成。当待排序的数组内的数值是均匀分配的时候，桶排序的时间复杂度为O(n)。

桶排序动画演示

假设有10个人给某个商品进行评分，评分的范围是0~1之间的小数，例如{0.6, 0.85, 0.9, 0.5, 0.35, 0.2, 0.1, 0.85, 0.8, 0.5} 这10个数据。一般没有特殊要求排序算法都是升序排序，小的在前，大的在后，效果如下：

桶排序分析

通过上面动画可以看出桶排序分为4个步骤：

1. 划分合适数量的桶。
2. 将所有待排序数据放入到对应的桶中。
3. 使用合理的算法对每个非空桶进行子排序。
4. 按顺序将每个桶中数据进行合并。

第一步：划分合适数量的桶

关于如何划分合适数量的桶，根据不同规模和不同范围的数据，我们采取不同的划分方式。目前数据都是0到1之间小数，数据比较均匀，我们等分成4个桶，每个桶的范围都是0.25，效果如下：

第二步：将所有待排序数据放入到对应的桶中

遍历待排序数据，将每个数据放入对应范围的桶中，效果如下：

第三步：使用合理的算法对每个非空桶进行子排序

待排序数据划分到不同桶中后，每个桶中的数据还是无序的，如下图所示：

从上图可以看到，第二个桶不用排序，其他桶需要进行排序，分别对每个桶中的数据再使用合适的排序算法，比如快速排序。排序后效果如下图：

第四步：4.按顺序将每个桶中数据进行合并

合并前效果如下图：

现在范围小的桶在前面，范围大的桶在后面，并且每个桶中的数据也是从小到大排序的，因此我们只需要从左往右将每个桶中的数据取出放到数组中即可。取出第一个桶后的数据如下：

取出第二个桶后的数据如下：

取出第三个桶后的数据如下：

取出第四个桶后的数据如下：

当所有桶中的数据都取出后排序就完成了。

桶排序代码编写

public class BucketSort {
    public static void main(String[] args) {
        double[] arr = {0.6, 0.85, 0.9, 0.5, 0.35, 0.2, 0.1, 0.85, 0.8, 0.5};

        bucketSort(arr);

        System.out.println("排序后: " + Arrays.toString(arr));
    }

    public static void bucketSort(double[] arr) {
        // 获取最大值和最小值
        double max = arr[0];
        double min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            double num = arr[i];
            if (num > max)
                max = num;
            else if (num < min)
                min = num;
        }

        // 桶的数量
        int bucketNumber = 4;

        // 每个桶的范围
        double range = (max - min) / bucketNumber;

        // 1.初始化所有桶,每个桶都是LinkedList,方便增加数据
        LinkedList<Double>[] buckets = new LinkedList[bucketNumber];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new LinkedList<>();
        }

        // 2.将所有待排序数据放入到对应的桶中
        for (int i = 0; i < arr.length; i++) {
            double num = arr[i];
            int index = (int) ((num - min) / range);
            if (index == bucketNumber)
                index -= 1; // 如果这个数字正好是最大值,计算出索引就是number,会数组越界,放到最后一个桶中
            buckets[index].add(num);
        }

        // 3.使用合理的算法对每个非空桶进行子排序
        for (int i = 0; i < buckets.length; i++) {
            // 对每个桶中的数据进行排序
            Collections.sort(buckets[i]);
        }

        // 4.按顺序将每个桶中数据进行合并
        int index = 0;
        for (int i = 0; i < buckets.length; i++) {
            LinkedList<Double> bucket = buckets[i];
            for (int j = 0; j < bucket.size(); j++) {
                arr[index] = bucket.get(j);
                index++;
            }
        }
    }
}

桶排序的局限性

如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，桶排序就退化为O(nlogn)的排序算法，如下图所示：

桶排序对待排序数据的要求是非常苛刻的，适用场景是在数据分布相对比较均匀或者数据跨度范围并不是很大时。如果数据跨度非常大，空间消耗就会很大。所以桶排序很少使用。

桶排序比较适合用在外部排序中

所谓的外部排序就是数据存储在外部磁盘中、数据量比较大、内存有限，无法将数据全部加载到内存中。比如说我们有50GB的订单数据，我们希望按订单金额进行排序，但是我们的内存有限只有几GB，没办法一次性把50GB的数据都加载到内存中。假设订单金额最小是0.1元，最大是10万元。可以将所有订单根据金额划分到100个桶里，第一个桶存储金额在0.1元到100元之内的订单，第二桶存储金额在101元到200元之内的订单，依次类推。每一个桶对应一个文件。订单金额在0.1元到10万元之间并不一定是均匀分布的，所以50GB订单数据是无法均匀地被划分到100个文件中的。有可能某个金额区间的数据特别多，划分之后对应的文件很大，没法一次性读入内存，针对某些划分之后还是比较大的文件，我们可以继续划分，比如订单金额在0.1元到100元之间的比较多，我们就将这个区间继续划分为10个小区间，0.1元到10元，11元到20元，21元到30元依次类推，然后将每个桶对应的数据读取到内存中使用快速排序进行排序，结果保存在文件中，最后合并到已排序的文件中。

桶排序的复杂度

1. 空间复杂度：数据规模为n，划分到k个桶中，总空间复杂度O(n + k)。
2. 时间复杂度：1.获取最大值和最小值，遍历数组，操作次数为n。2.初始化所有桶，操作次数为k。3.将所有待排序数据放入到对应的桶中操作次数为n。4.每个非空桶进行子排序使用时间复杂度为O(nlogn)的快速排序总操作次数为(k/n)*log(k/n)*k。5.按顺序将每个桶中数据进行合并操作次数n。所以总的时间复杂度为：3n+k+(k/n)*log(k/n)*k，因此时间复杂度为：O(n+k+logn-logk)。
3. 稳定性：稳定

总结

桶排序也是非基于比较的排序算法，将待排序数据按照一定的规则存放到对应的桶中，再进行排序与合并。桶排序可以对一定范围内的数据包括小数进行排序。桶排序可以突破基于比较排序算法的时间复杂度O(nlogn)。

桶排序的思想：将待排序数据分配到有限数量的桶里。每个桶再单独进行子排序，最后按顺序将多个桶中的数据进行合并，排序完成。当要被排序的数组内的数值是均匀分配的时候，桶排序的时间复杂度为O(n)。

桶排序对待排序数据的要求是非常苛刻的，适用场景是在数据分布相对比较均匀或者数据跨度范围并不是很大时。如果数据跨度非常大，空间消耗就会很大，如果数据都被划分到一个桶里，桶排序就退化为O(nlogn)的排序算法，所以桶排序很少使用。

桶排序比较适合用在外部排序中。

---------- End ---------- 原创文章和动画制作真心不易，您的点赞就是最大的支持！

想了解更多文章请关注微信公众号：表哥动画学编程