前言
本篇文章是排序算法系列的第五篇，学习三种非比较排序
后面这段话将作为排序算法系列博客每一篇的开头：
为避免文中过多赘述，写在最前面：
- 接下来所有的排序算法讲解中，无论是思路梳理，还是代码实现，都是最终实现从小到大排序，从大到小可以学会后自行类推。
- 都是使用int数组进行排序，数据总量为n
桶排序
桶排序的思想是计数排序和计数排序的基石，这里先介绍一下它
我更愿意将它称为桶思想，因为并不能通过桶排序这三个字就确定出一种唯一的排序算法的实现
这种思想本质上是一种分治，首先将一组数据分开，拆解成n组数据，再对这n组数据分别处理
那么桶排序的思想是怎么进行拆分的呢？
我总结来看，它的拆分要满足一个条件就可以——将拆成的n组数据保持分组区间有序
举个例子来说，比如一组数据的范围是在[0,1000]的闭区间，我把他拆成两组，A组[0,500)和B组[500,1000]，那么我们分别把A、B两组排序后再合并起来，整个数组就有序了，这个拆分的粒度可以更细一些，比如分成十组[0,100)......[900,1000]，这个拆分的过程，可以利用桶，只通过一次遍历就搞定，分多少组就准备多少个桶，遍历一次，将每个数据投入进它对应属于的桶即可，首先通过一个时间复杂度n完成分组有序，再继续组内使用其他方式排序，然后合并回来即可完成排序
看起来好像拆开了没什么用，每个桶里面还要排序，这又拆又合并好像反而会变慢的样子，其实完成的这个组间有序是不可小视的。
先分析一下时间复杂度：
对于待排序序列大小为 n，共分为 m 个桶，主要步骤有：
一个执行N次的循环，将每个元素装入对应的桶中
m次桶内排序，对每个桶中的数据进行排序（平均每个桶有 n/m 个元素）
一般使用较为快速的排序算法，让桶内排序的时间复杂度为 O(nlogn)，每个桶平均n/m个元素，把n替换成n/m
那么，整个桶排序的时间复杂度为：
T(n) = n + m*(n/m * log(n/m)) = n * ( log(n/m) + 1)
当 n = m 时，复杂度为 O(n)
可以认为，随着m的增大，时间复杂度会减小，趋于线性阶O(n)
然后，这里笔者偷个懒，没有自己去用代码测试，但其他人博客中都有证明过
这里直接放个结论。
- 随着桶数量的增加，排序性能有在慢慢提升（但是桶数量越大占用空间越大）
- 数据分布越均匀（各桶内数据量差不多），性能越好
对于桶的划分方式，就看不同的情况具体分析了，去平衡空间和时间
下面要介绍的，计数排序和基数排序，是两种特殊的桶划分方式
计数排序
桶排序是可以适合任何数据的，计数排序是一种特殊的桶排序，当待排序数据全是整数时，可以使用
对于一组有n个整数的数组来说，按照桶排序，将它划分为m组，进行排序，那么第一次遍历将数据放进要去的桶这个过程，会涉及到比较，每取出一个数据，都要判断它属于那个桶的范围，这个过程是可以被巧妙的省略掉的，省略的方式就是计数排序
举例，当我们确定一组数据arr在[0,100]这个范围，直接为每一个整数都准备一个桶，100个桶，用一个数组来表示bucket[100]，数组中存放一个int表示这个整数出现了多少次，那么每一个数据入桶的操作，只需要让 bucket[arr[i]]++ 即可完成入桶操作，然后再按桶的顺序出桶，就完成了排序
这里可以得出一个借结论，满足一个条件，即可进行计数排序，这个条件就是：必须是大于等于0的整数
因为数组下标索引是从0开始的
但其实有负整数也有办法解决问题，而且对所有整数数组排序，都需要这个操作，那就是个所有数据都减去一个最小值，整个数组就转化成一个从0开始的数组。
比如一组数据范围是[50,100]，没必要创建容量为100的数组，其实50就够了，所以个每个数据都减去50就好，再比如范围是[-50,0]，那么每个数据都减去（-50）
梳理一下技术排序的步骤
- 第一步，首先通过一次遍历，得到最大值和最小值，确定桶的范围，并创建出桶
- 第二步，再通过一次遍历，进行入桶操作
- 第三步，再通过一次遍历，这次是遍历桶，取出所有数据
这样三步排序就完成了
我们来算一下时间复杂度
n表示待排序数据量，m表示数据范围（桶容量）
第一次是遍历n，第二次也是遍历n，第三次是遍历m
T(n) = 2n+m => O(n) = n + m
几乎是线性阶，性能会随着m的减小而变快
下面上代码！
/**
* 计数排序
* @param arr 待排序数组
*/
public static void countSort(int[] arr){
//设置默认最大最小值
int min=arr[0];
int max=arr[0];
//找出最大，最小值
for (int value : arr) {
if (max < value) {
max = value;
}
if (min > value) {
min = value;
}
}
//创建计数数组
int[] countArr=new int[max-min+1];
//遍历待排序数组，确定每个数字的数量存入技术数组
for (int value : arr) {
countArr[value - min]++;
}
//遍历计数数组，把数据按顺序放回arr
int begin=0;
for (int i = 0; i < countArr.length; i++) {
if (countArr[i]!=0){
//有几个当前数字，就放几个
for (int j = 0; j <countArr[i] ; j++) {
arr[begin]=min+i;
begin++;
}
}
}
}
这里其实也可以看出，计数排序只能对纯数字数组进行排序，所以不牵扯稳定性的问题。
涉及到针对一个对象中某个属性进行对象数组排序，计数排序是完全无法使用的
除非每个桶不仅仅记录数据数量，把每个桶变成一个数组，真正存储每一个数据，这样每个桶要分配大量空间，空间复杂度本身就不低了，还要继续倍增。
所以虽然确实很快，但有一些局限性，看情况来使用
基数排序
基数排序，是一种非常巧妙的对桶排序思想的利用
我们来逐步讲解来让大家理解
-
首先从多属性排序开始
如果你有过开发经验，大家肯定都遇见过类似下面这种场景
比如我们从数据库查询一个list
每个数据有这些字段——id、name、排序字段、创建时间、修改时间
需要首先根据排序字段进行排序，如果排序字段相同，就要按照创建时间进行排序，如果创建时间也相同再按修改时间进行排序
这就属于是多个属性按不同优先级进行排序
这种场景要怎么实现呢？如果先按照最高优先级排序，就需要在遇到相同数据时，再去判断低一级的属性...，好像是有点麻烦。
有一种巧妙的思想，就是先按照最低优先级的属性排序一遍，然后再按照再高一级优先级的属性在保证稳定性的前提下排序一遍，一直到最高优先级也排序一遍，最终的结果就是满足要求的排序
-
如果你不知道什么是稳定性，那上一条最后一句肯定是没懂，所以再解释一下稳定性
稳定性就是，比如下面这组数字
31，44（a），44（b），86，18，28
有两个相同的44，给两个44打上标记，a号44和b号44
排好后两种可能：18,28,31,44(b),44(a),86 或 18,28,31,44(a),44(b),86
如果两个44，谁前谁后都不影响，那么排序的结果是正确的
但如果两个44还有其他属性，那么和排序前相比，结果被逆序了（b号44跑到a号44前面）这种就是不稳定的排序
稳定的排序就是，除了完成排序规则必须进行的顺序改变外，不改变原有的顺序
也就是两个数字相等的时候原先在前面的还在前面，原先在后面的还在后面，才叫稳定排序
那么上一条说的要保证稳定性，现在应该就能理解了，比如我们第一遍，先按照低优先级的，a在前b在后排的规则排好了序，让44(a)排在了44(b)的前面，再按照高优先级的数字排序，如果给打乱了，那么上一次的排序就失去了意义。
-
基数排序就是把这种多属性按不同优先级进行的排序，巧妙的应用在数字上面了
它将一个数字每一位都拆开（个位、十位、百位...都拆开），当成多个属性
低位数字优先级低，高位优先级高（很好理解，29和31，当然确定了十位数3比2大，就不需要管个位数谁大谁小了，21和29，在十位都是2，才去按个位排序）
也就是将一组数据的排序，拆解成了按不同优先级的多个一位数的排序
-
再结合到桶
一位数排序，就是0、1、2、3、4、5、6、7、8、9
如果我们准备是个桶，标号0-9
那么对某一个位的数，完成一次排序只需要遍历一遍，这个位的数字是几就放到几号桶，再按照桶的顺序取出来，就完成了按某位数的一次排序
最大的数是几位数，就进行几次排序，即可完成最终的排序
这个过程一定要注意稳定性，先入桶的要先出桶
分析一下时间复杂度：
首先第一步需要判断一次最大的数有多少位，一个n次的循环得到一个最大位数m
然后从低位到高位，进行m次排序，每次都循环入桶n次，出桶n次
所以T(n) = n + 2mn => O(n) = m * n
会随着m的减小增加性能
上代码！
代码中还是有一些实现细节在的，可以自行阅读以下，我都加了详细的注释
/**
* 非负整数基数排序
*
* @param arr 待排序数组（必须全是非负整数）
*/
public static void radixSort(int [] arr){
//1.先判断最大的数字有多少位
int maxNum = arr[0];
for (int i : arr) {
if (i>maxNum){
maxNum = i;
}
}
//根据最大数字的位数，排序非负整数数组
//最大数字的位数就是循环次数
int maxLength = (maxNum + "").length();
//2.准备好十个桶，这里采用二维数组即可bucketArr[10][arr.length+1]
// 多少行表示多少个桶，多少列表示一个桶的容量多大
// 每个桶容量都是待排序数组的长度是为了考虑极端情况，比如个位全是1十位全是2...
// 桶容量多出来的1是为了记录桶中实际存放的数据有多少，方便遍历桶内数据
int[][] bucketArr = new int[10][arr.length + 1];
//3.按不同优先级循环排序
// 要想获取到arr数组中，每个数字从右往左数第i+1个数字，需要外层定义一个n=1,每次循环后n*10
// 才能用数字/n 再 %10 得到对应位的一位数
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
//遍历待排序数组
for (int num : arr) {
//拿到对应位数的数字
int oneNum = num / n % 10;
//放进对应桶中，每个桶第一位用于存放桶中实际存放了几个数据，初始化就是0，数据从索引1开始存
bucketArr[oneNum][++bucketArr[oneNum][0]] = num;
}
//再从下标0-9的桶中依次取出来放回原数组，先放的先取，从索引1开始取
// 记录原数组该放的位置
int index = 0;
for (int j = 0; j < 10; j++) {
for (int x = 1; x <= bucketArr[j][0]; x++) {
arr[index++] = bucketArr[j][x];
}
}
// 全部放回去之后判断不是最后一次就重置每个桶第一个位置的记录值
if (i < maxLength - 1) {
for (int j = 0; j < 10; j++) {
bucketArr[j][0] = 0;
}
}
}
}
这里可以看到只能是非负整数的排序，能不能支持负整数呢
其实也是可以的，只需要像前面计数排序中同样把每个数减去最小值就可以转换为非负整数了
/**
* 基数排序对负整数的支持
*
* @param arr 待排序数组
*/
public static void radixSortPlus(int[] arr){
//1.判断最小的数字是否是负数，如果不是就按正整数处理，如果是，就获取这个值
int minNum = arr[0];
//在一个循环中，获取到最小的数字
for (int i : arr) {
if (i<minNum){
minNum = i;
}
}
//如果最小的数字是负数,遍历数组，给所有数字减去这个负数（相当于加上这个数的绝对值）
if (minNum<0){
for (int i = 0; i < arr.length; i++) {
arr[i]-=minNum;
}
}
//减去最小的负数后，整个数组被转换为非负整数了，进行非负整数的基数排序
radixSort(arr);
//排序结束后，如果最小的数字是负数，再遍历数组，给每个数据加上这个负数（相当于减去这个数的绝对值）
if (minNum<0){
for (int i = 0; i < arr.length; i++) {
arr[i]+=minNum;
}
}
}
总结
以上就是三种接种桶的排序，以空间为代价，降低了时间复杂度，几乎接近了线性阶。
其次，也都有一定的局限性和偏向性
比如计数排序最大位数小时性能很好，计数排序数据范围小时性能很好
可以根据不同的情况来选择排序算法使用
按照之前四篇的惯例，都还会进行性能测试
这里因为之前的测试数据被弄丢了，偷个懒就不再测一遍了，反正比之前比较排序都快就是了
然后，可以在排序算法系列下一篇性能比较中看到最新的所有排序性能测试结果
评论
暂无评论，抢个沙发？