看动画学算法之:排序-基数排序

简介

之前的文章我们讲了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; 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