到目前为止我已经把一些常见的排序算法进行了讲解。今天主要关注另外一个排序算法，叫做基数排序。
每天学一个知识点，一年之后就会有质的变化。
一、原理
1、计数排序
在正式开始讲解基数排序之前，我们先介绍一个和它同名不同字的排序算法，叫做计数排序。这个计数排序跟基数排序可不一样。可别搞混了。
计数排序的思想是这样的：
对每一个输入元素，计算小于它的元素个数，如果有N个元素小于它，那么它就应该放在N+1的位置上。
也就是说，计数排序其实就是根据大小确定一下在整个数组中的位置。如果理解了之后，我们就开始讲一下今天的基数排序。
2、基数排序
相信我们都有查字典的经历，假设我们要查一个字，首先我们根据拼音首字母确定位置，然后根据拼音的第二个字母进一步确定位置，然后根据拼音的第三个字母再进一步确定，就这样一直确定到最后一个字母，直接翻到指定的页码。基数排序就是这样一个思想：
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。首先从最高位开始排序，接着以此降低，一直到个位。此时整个序列有序。
我们给一张动图来表示一下：
1-原理.gif
上面动图中是这样的排序过程。
（1）第一步：对原始序列按照十位数的大小，分别存放在0到9一共10个桶中。
（2）第二步：对每个桶中的元素，按照个位数进行再排序。
这就是基数排序的整个排序过程。这里还要说一下，我们是从最高位开始往最低位开始进行排的，这叫做MSD。而如果我们从最低位开始往最高位排，叫做LSD。LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。我们知道就OK了。下面我们就使用代码来实现一下。
二、实现
对于代码的实现，我一直以来的思路就是根据其原理，只要原理弄清楚了，代码实现就轻松多了。
//第一点：d表示1、10、100等，序列的最大值长度是2，d就是100。
private static void radixSort(int[] array, int d) {
int n = 1;
int k = 0;
//从0到9一共10个桶，每个桶最多有array.length个元素。
int[][] bucket = new int[10][array.length];
//order表示具体某一个桶
int[] order = new int[array.length];
//第二点：只要n小于d，则一直基数排序
while (n < d) {
//第三点：将序列的每个数字放在相应的桶里
for (int num : array) {
int digit = (num / n) % 10;
bucket[digit][order[digit]] = num;
order[digit]++;
}
//第四点：将上一次排序的结果覆盖到原数组中
for (int i = 0; i < array.length; i++){
//第五点：如果这个桶有数据，依次取出来放到原数组array中。
if (order[i] != 0){
for (int j = 0; j < order[i]; j++) {
array[k] = bucket[i][j];
k++;
}
}
order[i] = 0;// 将桶里计数器置0，用于下一次位排序
}
n *= 10;
k = 0;// 将k置0，用于下一轮保存位排序结果
}
}
到了这里你会发现一个问题，那就是整个排序过程，没有比较元素之间的大小，只是根据每个数字放在不同的桶里面，放了几遍之后再依次拿出来就是有序的，因此基数排序也叫作“不基于比较”的排序算法。
对于改进，我们该如何考虑呢？
（1）如果我们的数据长度跨度比较大，比如说里面不仅包含了1000，还包含了10000000，这时候如果我们选择以10位基数，那么比较的轮数就会很大，这时候我们可以增大基数。这种方式适合对LSD的改进。
（2）从上面动图中的例子，相信你也会发现，有时候在桶中的元素，明明已经有序了，不过我们还是进入到下一轮进行基数排序了。这时候我们可以增加一个flag，如果在基数为100的时候每个桶内基数排序之后已经有序了，那就没有必要进行下一轮基数为10的排序了，这种适合MSD的改进。
谢谢支持，对于基数排序的改进，一直是一个大难题。因为在改进的时候我们需要从两方面考虑，一个是时间复杂度一个是空间复杂度。这里的两个改进思想有一部分也是我参考了网络上其他人的，还问了某某网的HR。
对于时间复杂度的改进，我们主要关注于移动次数和比较次数，在这里基数排序没有比较，但是我们可以尽量减少移动。移动就要保存临时元素，这就要在考虑空间复杂度。当然了还有一点，那就是和其他排序算法结合。来进一步提高。
基数排序的时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数。另外基数排序法是属于稳定性的排序。
如有问题，欢迎指正。不喜勿喷。
默认标题_方形二维码_2019.08.16.png
网友评论