简介之前的文章我们讲了count排序 ， 但是count排序有个限制 ， 因为count数组是有限的 ， 如果数组中的元素范围过大 ， 使用count排序是不现实的 ， 其时间复杂度会膨胀 。
而解决大范围的元素排序的办法就是基数排序 。
基数排序的例子什么是基数排序呢？
考虑一下 ， 虽然我们不能直接将所有范围内的数字都使用count数组进行排序 ， 但是我们可以考虑按数字的位数来进行n轮count排序 ， 每一轮都只对数字的某一位进行排序 。
最终仍然可以得到结果 ， 并且还可以摆脱count数组大小的限制 ， 这就是基数排序 。
假如我们现在数组的元素是：1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793 。
先看动画 ， 看下最直观的基数排序的过程：
文章插图
在上面的例子中 ， 我们先对个位进行count排序 ， 然后对十位进行count排序 ， 然后是百位和千位 。
最后生成最终的排序结果 。
基数排序的java代码实现因为基数排序实际上是分别按位数的count排序 。 所以我们可以重用之前写的count排序的代码 ， 只是需要进行一些改造 。
doCountingSort方法除了传入数组外 ， 还需要传入排序的位数digit ， 我们用1 ， 10 ， 100 ， 1000来表示 。
看一下改造过后的doCountingSort方法：
public void doRadixSort(int[] array, int digit){int n = array.length;// 存储排序过后的数组int output[] = new int[n];// count数组 ， 用来存储统计各个元素出现的次数int count[] = new int[10];Arrays.fill(count,0);log.info("初始化count值:{}",count);// 将原始数组中数据出现次数存入count数组for (int i=0; i=0; i--){output[count[(array[i]/digit)%10]-1] = array[i];count[(array[i]/digit)%10]--;}log.info("构建output之后的output值:{}",output);//将排序后的数组写回原数组for (int i = 0; i跟count排序变化不大 ， 区别就是这里我们需要使用count[(array[i]/digit)%10] ， 来对每一位进行排序 。
另外 ， 为了计算出位数digit的值 ， 我们还需要拿到数组中最大元素的值：
public int getMax(int[] array){int mx = array[0];for (int i = 1; i < array.length; i++)if (array[i] > mx){mx = array[i];}return mx;}看下怎么调用：
public static void main(String[] args) {int[] array= {1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793};RadixSort radixSort=new RadixSort();log.info("radixSort之前的数组为:{}",array);//拿到数组的最大值 ， 用于计算digitint max = radixSort.getMax(array);//根据位数 ， 遍历进行count排序for (int digit = 1; max/digit > 0; digit *= 10){radixSort.doRadixSort(array,digit);}}看下输出结果：
文章插图
很好 ， 结果都排序了 。
基数排序的时间复杂度从计算过程我们可以看出 ， 基数排序的时间复杂度是O(d*(n+b))， 其中b是数字的进制数 ， 比如上面我们使用的是10进制 ， 那么b=10 。
d是需要循环的轮数 ， 也就是数组中最大数的位数 。 假如数组中最大的数字用K表示 ， 那么d=logb(k) 。
综上 ， 基数排序的时间复杂度是O((n+b) * logb(k)) 。
当k <= nc ， 其中c是常量时 ， 上面的时间复杂度可以近似等于O(nLogb(n)) 。
考虑下当b=n的情况下 ， 基数排序的时间复杂度可以近似等于线性时间复杂度O(n) 。
【看动画学算法之：排序 - 基数排序】本文为阿里云原创内容 ， 未经允许不得转载 。