极客算法训练笔记(九)，十大经典排序之桶排序，实习第一个业务就是分桶实现的

目录

• 十大经典排序算法江山图
• 大转盘抽奖之分桶实现
• 桶排序
  • 桶排序场景
  • 算法思想
  • 图解桶排序
  • 代码实现
  • 时间复杂度分析
  • 空间复杂度分析
  • 稳定性分析
  • 适用条件

十大经典排序算法江山图

十大经典排序算法江山图

十大排序分类

如上图所示（图来自于极客时间算法训练营超哥的资料），我之前写的七大排序算法，都是比较类排序，最后三种是时间复杂度是O(n)的非比较类排序算法:桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序(Linear sort)。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。

这几种排序算法理解起来都不难，时间、空间复杂度分析起来也很简单，但是对要排序的数据要求很苛刻，所以弄清楚这三种排序的适用场景是重点。

大转盘抽奖之分桶实现

我想到了我实习负责写的第一个业务，就是大转盘抽奖，实现的核心抽奖算法其实就是用的分桶。

业务场景：一个抽奖活动里面有很多个奖品，每个奖品的中奖率都不一样，其中的未中奖也相当于一种奖品，所有奖品中奖率加起来和是1，外表如下所示，想玩玩的朋友可以一键到达 http://shop386997.kuaizhan.com/pages/marketing-package/fortune-wheel/fortune-wheel?id=5fd5b484fa079a000618c65a

大转盘抽奖

例如上图中，积分奖品，优惠券奖品，赠品奖品三种奖品概率分别为20%，20%，30%，那么未中奖概率是30%。

我的实现：每次抽奖都生成一个1～100的随机数，根据每个奖品后台设置的中奖概率的大小进行分桶，随机数在1～20代表中奖积分，在20～40内的数代表中奖优惠券，40～70内代表中奖赠品，70～100内的随机数代表未中奖，这就是抽奖算法的核心实现，这其实和分桶差不多，将100内的数分为了四个桶。

桶排序

桶排序场景

比如说我们有10GB的订单数据，我们希望按订单金额(假设金额都是正整数)进行排序，但是我们的内存有限，只有几百MB，没办法一次性把10GB的数据都加 载到内存中。这个时候该怎么办呢?

1. 我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是1元，最大是10万元。我们将所有订单根据金额划分到100个桶里，第一个桶我们存储金额在1元到1000元之内的订单，第二桶存储金额在1001元到2000元之内的订单，以此类推。每一个桶对应一个文件，并且按照 金额范围的大小顺序编号命名(00，01，02...99)。
2. 理想的情况下，如果订单金额在1到10万之间均匀分布，那订单会被均匀划分到100个文件中，每个小文件中存储大约100MB的订单数据，我们就可以将这100个小 文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文 件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。
3. 不过，你可能也发现了，订单按照金额在1元到10万元之间并不一定是均匀分布的 ，所以10GB订单数据是无法均匀地被划分到100个文件中的。有可能某个金额区间的数据特别多，划分之后对应的文件就会很大，没法一次性读入内存。这又该怎么办呢?
4. 针对这些划分之后还是比较大的文件，我们可以继续划分，比如，订单金额在1元到1000元之间的比较多，我们就将这个区间继续划分为10个小区间，1元 到100元，101元到200元，201元到300元...901元到1000元。如果划分之后，101元到200元之间的订单还是太多，无法一次性读入内存，那就继续再划分，直到所有的文件都能读入内存为止。

算法思想

桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序（有可能再使用别的排序算法或是以递归方式 继续使用桶排序进行排），桶内排完序后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。颇有点大事化小，小事化了的感觉

图解桶排序

图解桶排序

值得注意的是，桶的个数是人为指定的，不随着数组大小和数值大小改变（例如上面的例子中，可以根据文件大小和内存大小，得到桶的个数）。

桶内的数据范围是 (max-min)/k 因为最后一组的原因向上取整，k是桶的个数，这个地方是（46-4)/5 向上取整得到9。

步骤：

1. 先进行数组的最大最小值的扫描，得到最值；
2. 计算每个桶的额分区范围；
3. 遍历原数组，将每个值放到对应范围的桶内，按照桶读取数据就是有序的了；

代码实现

这里假设每个桶的大小为5，代码实现如下：

import java.util.ArrayList;
import java.util.Collections;


/**
 * @author by zengzhiqin
 * 2020-12-13
 */
public class BucketSort {

    public static int[] bucketSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }

        int length = arr.length;
        double max = arr[0];
        double min = arr[0];
        // 数组的最大值与最小值
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] < min) {
                min = arr[i];
            }

            if(max < arr[i]) {
                max = arr[i];
            }

        }

        // 桶的初始化
        int bucketNum = 5;
        // 每个桶内还是数组
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new ArrayList<>());
        }

        // 分区大小
        double section = Math.ceil((max - min) / 5);
        // 数据入桶
        for (int i = 0; i < length; i++) {
            // 桶的序号
            double bkt = Math.floor((arr[i] - min) / section);
            System.out.println(arr[i] + " 这个数放到 " + (int)bkt + " 号桶");
            bucketList.get((int)bkt).add(arr[i]);
        }

        // 对每个桶内的元素进行排序，使用jdk自带的排序算法，具体的源码分析我上一篇文章写了（根据数据个数各种排序组合使用）
        for (int i = 0; i < bucketNum; i++) {
            Collections.sort(bucketList.get(i));
        }

        // 把每个桶排序好的数据进行合并汇总放回原数组
        int index = 0;
        int i=0;
        for(ArrayList<Integer> arrayList : bucketList){
//            System.out.print(i + "第几组");
            for(int value : arrayList){
//                System.out.println(value);
                arr[index] = value;
                index++;
            }
        }

        return arr;
    }


    public static void main(String[] args) {
        int[] arr = {21,4,12,42,46,23,27,11,6,5,33,29,41,46,40,13,31};

        arr = bucketSort(arr);
        System.out.print("数组排序之后：");
        for (int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + "，");
        }

    }

}

桶排序结果

根据这个图回去看上面图解分桶中，桶里面的数据是不是如此，这里是先进行了一遍数组值的大小扫描，实际开发中很多业务场景下，我们自己知道数据的最大最小范围，例如

时间复杂度分析

假设要排序的数据有n个，均匀地划分到 k 个桶内。

1. 遍历所有元素入桶过程，时间复杂度为O(n);
2. 遍历每个桶，进行排序，如果每个桶内只有一个元素，时间复杂度O(k);
3. 总的为 O(n+k);

实际上，这个还取决于桶内排序算法，如果每个桶内元素很多，假设使用的桶内快排，实际的时间复杂度要比这个大。

看起来很美好，但是这是建立在美好假设的情况下，桶排序对排序的数据要求是非常苛刻的，下面看下桶排序的数据条件：

1. 数据值比较均匀，在各个桶之间分布就比较均匀；
2. 能确定数据的范围，数据的跨度不会特别大； 第一条，如果桶排序之后有些桶数据特别多，有些特别少，那么数据量多的桶内数据排序时间复杂度就会很高 第二条，数据跨度特别大，容易引起数据分布不均，例如总共就5个数，0，10000，1000000，10000000，1000000000，这样就很不好分桶，也就不适合桶排序。

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

空间复杂度分析

O(n+k)。

稳定性分析

稳定。数据进桶时可以控制相同元素的先后顺序保持不变。

适用条件

用于均匀分布的数字数组.

往期类似推荐：

极客算法训练笔记(八)，十大经典排序之堆排序，被树耽误的数组

极客算法训练笔记(七)，十大经典排序之归并排序，全网最详

极客算法训练笔记(六)，十大经典排序之希尔排序，快速排序

极客算法训练笔记(五)，十大经典排序之冒泡，选择，插入排序

欢迎点赞分享在看，关注公众号《阿甘的码路》看更多内容，有问题可以加我微信私我指正，各大平台也会同步只不过排版可能有些会不太一样～

参考资料：极客时间算法训练营资料，数据结构与算法之美