目录导航
# 介绍 百度百科：基数排序(radix sort)属于"分配式排序"，又称桶子法。它是透过键值的部分资讯，将要排序的元素分配至某些"桶"中以达到排序的作用，基数排序是属于稳定性的排序，时间复杂度为`O(nlog(r)m)`，`r`为所采用的基数，m为堆数，在某些时候，基数排序的效率高于其他的稳定性排序。简单地说，基数排序是一种通过关键字之间的比较和移动记录这两种操作，而实现基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法==。
基数排序可视化过程
实现思路
这里假设有这样一个数据：[123、12、90、5]
跟着我的思路实现一次基数排序试试！
我会开辟一个map和很多个队列，队列用来存放已经排好序的元素，map用来映射数位和的对应的队列，当数位已经是最大数的数位时，比如上述数据中，123就是最大的值，所以我遍历到第3次时整个排序就完毕，最后出列的数据一定是已排序好的。
1、第一趟普通遍历，获取最大的数的位数。这样可以确定第二趟遍历的次数。这里最大数是123，所以最大位数为3，则第二趟遍历次数为3.
2、第二趟遍历，进行倒数第1位的收集(最大数是3位，允许遍历)：
0:[90]
2:[12]
3:[123]
5:[5]
第1趟后的结果：90,12,123,5
3、第二趟遍历，进行倒数第2位的收集(最大数是3位，允许遍历)：
0:[5]
1:[12]
2:[123]
9:[90]
第2趟后的结果：5,12,123,90
4、第二趟遍历，进行倒数第3位的结果(最大数是3位，刚好达到最大位，允许遍历)
0:[5,12,90]
1:[123]
0对应的队列出列后为：5,12,90
所以第3趟后的结果：5,12,90,123
排序完毕，可以看到第2,3,4步可以总结为1步：数组arr中，以第i位为基数进行一轮排序，这个i位就是一个每个数组中元素的单个关键字，排序完所有的关键字最终的结果一定是排序好的。
上代码
先说一下我写这个代码的思路，为了让这个代码看起来较"优雅"，我着实花了点时间。
主核心代码是redixSort和radixSingle，radixSingle是实现单趟以i位为基数的一次排序，redixSort则是经过第一次的遍历获取到最大数的位数之后，循环进行无数次单趟排序后的结果。最后由out函数输出。
其中的一个工具函数"pos"，作用是获取一个数的第i位的数，位数从右往左分别是1,2,3,4...。比如pos(1234, 3)则会返回2。
下面就是我的代码：
public static void main(String[] args) {
int[] arr = {10, 6, 3, 8, 33, 27, 66, 9, 7, 88};
out("排序前的数组：", arr);
radixSort(arr);
out("排序后的数组：", arr);
}
/**
* 以所有位为基数进行基数执行d次排序
*/
public static void radixSort(int[] arr) {
// 1. 第一趟遍历获取最大的数的长度
int maxLength = 0;
for (int i : arr) {
maxLength = Math.max(String.valueOf(i).length(), maxLength);
}
// 2. 由1确定好了d然后执行d轮排序。O(d)
for (int i = 1; i <= maxLength; i++) {
radixSingle(arr, i);
}
}
/**
* 以pos位为基数进行一趟排序
*/
public static void radixSingle(int[] arr, int pos) {
// 选用TreeMap是因为它内部就是一颗红黑树，天然自带排序的功能，TreeMap自带的排序时间复杂度为O(logn)。
// 1. 收集基数O(n)
Map<Integer, Queue<Integer>> map = new TreeMap<>();
for (int i = 0; i < arr.length; i++) {
map.put(pos(arr[i], pos), new LinkedList<>());
}
// 2. 往对应的桶里加入数据O(n)
for (int i = 0; i < arr.length; i++) {
Queue queue = map.get(pos(arr[i], pos));
queue.add(arr[i]);
}
// 3. 赋值，这一步可以省略，不计入时间复杂度。O(n)
AtomicInteger m = new AtomicInteger(0);
map.forEach((k,q) -> q.forEach((i) -> arr[m.getAndIncrement()] = i));
}
/**
* @param text 提示文本
* @param arr 待输出数组
*/
public static void out(String text, int[] arr) {
System.out.println(String.join("", text, Arrays.toString(arr)));
}
/**
* 获取一个数pos位上的值
*/
public static int pos(int num, int pos) {
return (num % (int)Math.pow(10, pos)) / (int)Math.pow(10, pos-1);
}
运行情况：
排序前的数组：[10, 6, 3, 8, 33, 27, 66, 9, 7, 88]
排序后的数组：[3, 6, 7, 8, 9, 10, 27, 33, 66, 88]
效率分析
引入百度百科的定义，设待排序序列为n个记录，d个关键字码，关键字码取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共d趟分配和收集。空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。
我来大致解释一下，我代码中d指的是radixSort中maxLength的值，也就是数组元素中最大数的位数，因为后续会执行最大位长度的那么多趟排序。
而看到radixSingle函数中，我先一个for循环收集关键字，也就是每个数组元素的第i位的数，这个数被称为"关键字“，比如[123,12]这个数据中，第一趟(d=1)时，桶里面的key分别为[2:[12],3:[123]]，仔细思考一下是不是这样的。
再继续分析，我为了省事，直接使用TreeMap进行收集，收集的时间复杂度为O(n)，TreeMap内部会自动以key为标准进行排序，但是排序的时间复杂度为O(logn)，所以这一部分的时间复杂度还是为O(n)。
这样就确定了收集部分的时间复杂度为O(n)，假设我们基数有radix个，我称之为桶，radix就是桶的个数，我得往每个桶里面存数据，这一部分的时间复杂度为O(n)，与百度百科上说的O(radix)不符，原因是因为java的问题，由于radix<n的，元素入桶这个操作是可以简化到O(radix)，但是我为了使代码简洁，人人都看得懂所以就直接一趟O(n)的遍历，总的来说radixSingle时间复杂度为O(2n)，这个是可以达到O(radix+n)的，对于radixSort函数来说，时间复杂度为O(d)，所以我代码总的时间复杂度为O(2dn)=O(dn)。
关于空间，基数的存储占radixd个，存完基数还得存数据，数据占n个，所以空间复杂度是O(radixd+n)
其实我也对这个时间复杂度的计算结果不太确定，所以咨询了算法老师，得出的结论是基数排序一般都是O(dn)，而不是百度百科上说的O(d(radix+n))，所以，我是对的。当然百度也没毛病，确实也是O(radix+n)，radix可以趋近于n或者趋近于n/2或者趋近于1，然而不管他趋近于多少，最终计算时间复杂度只能二选其一，所以要么是O(radix)或O(n)，但由于radix<n，所以，这里只需要计入O(n)即可。！
时间复杂度和空间复杂度的测试
为了能准确的测试数据量特别大的时候能直接反应出时间和空间变化，这里我将代码重新更正：
public static void main(String[] args) {
int[] arr = RandomData.create(1).random().toArray();
RadixSort radix = Proxy.proxy(new RadixSort(), new RadixSortAspect());
System.gc();
System.out.println("待排序数量:" + arr.length + "(个)");
radix.sort(arr);
System.gc();
}
public static void sort(int[] arr) {
int d = 0;
for (int i : arr) {
d = Math.max(i, d);
}
d = String.valueOf(d).length();
Queue<Integer>[] bucket = new LinkedList[10];
for (int i = 0; i < bucket.length; i++) {
bucket[i] = new LinkedList<Integer>();
}
for (int pos = 1; pos <= d; pos++) {
for (int j = 0; j < arr.length; j++) {
Queue queue = bucket[pos(arr[j], pos)];
queue.add(arr[j]);
}
int c = 0;
for (int j = 0; j < bucket.length; j++) {
while (!bucket[j].isEmpty()) {
arr[c++] = bucket[j].poll();
}
}
}
}
可以看到，我将基数排序的两个步骤合二为了一，花了点功夫实现了一个动态代理，可以通过切面用来监听sort方法的运行时间和cpu占用情况等等。如果需要代码我会将代码放至github上。
接下来我会从1开始随机生成数据，规模会成倍增大然后分析运行情况。
下面仔细看好了！
排序数：1
待排序数量:1(个)
调用sort前系统内存:2.35MB/123.00MB
调用sort前内存使用率:0.02%
排序轮数(d):1
调用sort后系统内存:3.00MB/123.00MB
调用sort后内存使用率:0.02%
调用sort所消耗的时间:17毫秒
排序数：10
待排序数量:10(个)
调用sort前系统内存:2.35MB/123.00MB
调用sort前内存使用率:0.02%
排序轮数(d):1
调用sort后系统内存:3.00MB/123.00MB
调用sort后内存使用率:0.02%
调用sort所消耗的时间:18毫秒
排序数：100
待排序数量:100(个)
调用sort前系统内存:2.35MB/123.00MB
调用sort前内存使用率:0.02%
排序轮数(d):2
调用sort后系统内存:3.00MB/123.00MB
调用sort后内存使用率:0.02%
调用sort所消耗的时间:17毫秒
排序数：1000
待排序数量:1000(个)
调用sort前系统内存:2.35MB/123.00MB
调用sort前内存使用率:0.02%
排序轮数(d):3
调用sort后系统内存:3.00MB/123.00MB
调用sort后内存使用率:0.02%
调用sort所消耗的时间:19毫秒
排序数：10000
待排序数量:10000(个)
调用sort前系统内存:2.39MB/123.00MB
调用sort前内存使用率:0.02%
排序轮数(d):4
调用sort后系统内存:6.94MB/123.00MB
调用sort后内存使用率:0.06%
调用sort所消耗的时间:37毫秒
排序数：100000
待排序数量:100000(个)
调用sort前系统内存:2.73MB/123.00MB
调用sort前内存使用率:0.02%
排序轮数(d):5
调用sort后系统内存:28.46MB/123.00MB
调用sort后内存使用率:0.23%
调用sort所消耗的时间:185毫秒
排序数：1000000
待排序数量:1000000(个)
调用sort前系统内存:6.80MB/155.50MB
调用sort前内存使用率:0.04%
排序轮数(d):6
调用sort后系统内存:111.89MB/350.50MB
调用sort后内存使用率:0.32%
调用sort所消耗的时间:1791毫秒
排序数：10000000
待排序数量:10000000(个)
调用sort前系统内存:41.55MB/558.50MB
调用sort前内存使用率:0.07%
排序轮数(d):7
调用sort后系统内存:744.04MB/1231.00MB
调用sort后内存使用率:0.60%
调用sort所消耗的时间:28924毫秒
排序数：30000000
待排序数量:30000000(个)
调用sort前系统内存:120.07MB/1354.50MB
调用sort前内存使用率:0.09%
排序轮数(d):8
调用sort后系统内存:1354.98MB/1668.00MB
调用sort后内存使用率:0.81%
调用sort所消耗的时间:140594毫秒
后面5000w就就GG了，直接OOM，我怕电脑蓝屏所以就不测试了。。。（目测5000w数会占到2G，1亿个数内存大概会飞到4.78G）
结论
由于咱得到的时间和空间并不是"纯净"的，比如我产生随机数用的ArrayList，之后用流数组转换成int数组，这样空间部分会一直存在于内存中。而数据量规模很大时，内存不不够用，JVM会向系统申请内存，所以消耗的时间也会正比例增加。但我们还是可以略微找一下规律。
找一下规律：
从1百万-1千万，n的规模增长了10倍，时间增加了16倍，空间增加了7倍。可以算出，每增长一倍，时间会增加1.6倍，空间会增加0.7倍。
从1千万-3千万，n的规模增长了3倍，时间增加了4.8倍，空间增加了1.75倍。可以算出，每增长一倍，时间会增加1.6倍，空间会增加0.58倍。
为什么只寻找大数的规律？我发现jvm为了优化效率和内存使用率，会自行做一些操作，比如申请内存，可以看到100w和1000w的内存上界是不一样的。jvm有时还会频繁gc影响时间，但也省下了内存开销。为了读取的效率，jvm会设置很多层缓存，这也是为什么1w之前的空间和时间无差别。后续jvm扩容后还是会缓存一些常用数据和代码（为了加快经常性事件），所以时间和空间的计算我只能往最大了选，这样可以减小固件部分的分子，代码部分的空间和时间数据会更明显。
即便接下来不用跑代码按照这个规律也可以得出规模每增长时，时间和空间都会增加一个固定的比值，所以看得出来是成线性增长的。这也证明了时间复杂度是O(dn)没有问题。但需要注意一下这个d，总的来说在我规定的这个排序中，这个d也是可以看做常量的。对于数的排序来说，d的取值为范围1-10，相较于n的规模无限增大，dn会趋近于n，d可以忽略掉。在我这的这个基数排序中时间复杂度为O(n)也是正确的。
但需要注意一下，基数排序是多关键字排序，我如果以1-9为基数去分桶，d的值可以忽略，但我可以让桶元素去趋近于n，这样就是一个θ(logn)的插入和一个θ(n)的poll操作，复杂度又变成了o(nlogn)。但问题来了，上面所说基数排序为什么可以到达O(n)？O(nlogn)的下界是针对于比较排序而言的，基数排序不是基于比较，而是基于数据分配，所以可以突破下界。
为啥基数排序并没有很普及的使用？基数排序在某些场景下应该要比快速排序快的，但是除了考虑时间的问题还得考虑空间问题，快速排序缓存友好，归并的过程的没有使用额外的空间，在java中得注意，内存过大会引起full gc，频繁full gc会引起系统卡顿。而且基数排序只适用于有基数的情况，基于比较的排序适用于所有的情况，比如java里直接实现Comparator接口即可实现对任意对象的排序。
之后我在介绍快速排序时会与基数排序进行一个详细的比较。
应用场景
并行基数排序速度非常快，超算上的数据库都是使用基数排序。
后面会尝试实现一遍并行基数排序（目测效果应该很一般==!）
