目录

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

十大经典排序算法江山图

十大经典排序算法江山图

十大排序分类

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

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

大转盘抽奖之分桶实现

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

业务场景：一个抽奖活动里面有很多个奖品，每个奖品的中奖率都不一样，其中的未中奖也相当于一种奖品，所有奖品中奖率加起来和是1，外表如下所示，想玩玩的朋友可以一键到达

大转盘抽奖

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

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

桶排序桶排序场景

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

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

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

图解桶排序

图解桶排序

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

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

步骤：

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

这里假设每个桶的大小为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 个桶内。

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

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

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

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

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

空间复杂度分析

O(n+k)。

稳定性分析

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

适用条件

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

往期类似推荐：

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

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

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

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

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

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