目录
- 十大经典排序算法江山图
- 大转盘抽奖之分桶实现
- 桶排序
- 桶排序场景
- 算法思想
- 图解桶排序
- 代码实现
- 时间复杂度分析
- 空间复杂度分析
- 稳定性分析
- 适用条件
十大经典排序算法江山图
十大排序分类
如上图所示（图来自于极客时间算法训练营超哥的资料），我之前写的七大排序算法，都是比较类排序，最后三种是时间复杂度是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元，最大是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，代码实现如下：
importjava.util.ArrayList;
importjava.util.Collections;
/**
*@authorbyzengzhiqin
*2020-12-13
*/
publicclassBucketSort{
publicstaticint[]bucketSort(int[]arr){
if(arr==null||arr.length<2){
returnarr;
}
intlength=arr.length;
doublemax=arr[0];
doublemin=arr[0];
//数组的最大值与最小值
for(inti=1;i<arr.length;i ){
if(arr[i]<min){
min=arr[i];
}
if(max<arr[i]){
max=arr[i];
}
}
//桶的初始化
intbucketNum=5;
//每个桶内还是数组
ArrayList<ArrayList<Integer>>bucketList=newArrayList<>(bucketNum);
for(inti=0;i<bucketNum;i ){
bucketList.add(newArrayList<>());
}
//分区大小
doublesection=Math.ceil((max-min)/5);
//数据入桶
for(inti=0;i<length;i ){
//桶的序号
doublebkt=Math.floor((arr[i]-min)/section);
System.out.println(arr[i] "这个数放到" (int)bkt "号桶");
bucketList.get((int)bkt).add(arr[i]);
}
//对每个桶内的元素进行排序，使用jdk自带的排序算法，具体的源码分析我上一篇文章写了（根据数据个数各种排序组合使用）
for(inti=0;i<bucketNum;i ){
Collections.sort(bucketList.get(i));
}
//把每个桶排序好的数据进行合并汇总放回原数组
intindex=0;
inti=0;
for(ArrayList<Integer>arrayList:bucketList){
//System.out.print(i "第几组");
for(intvalue:arrayList){
//System.out.println(value);
arr[index]=value;
index ;
}
}
returnarr;
}
publicstaticvoidmain(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(inti=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)。
稳定性分析稳定。 数据进桶时可以控制相同元素的先后顺序保持不变。
适用条件用于均匀分布的数字数组.
往期类似推荐：
极客算法训练笔记(八)，十大经典排序之堆排序，被树耽误的数组
极客算法训练笔记(七)，十大经典排序之归并排序，全网最详
极客算法训练笔记(六)，十大经典排序之希尔排序，快速排序
极客算法训练笔记(五)，十大经典排序之冒泡，选择，插入排序
欢迎点赞分享在看，关注公众号《阿甘的码路》看更多内容，有问题可以加我微信私我指正，各大平台也会同步只不过排版可能有些会不太一样～
参考资料：极客时间算法训练营资料，数据结构与算法之美
