简介

之前的文章咱们讲了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<n; ++i) {            count[(array[i]/digit)%10]++;        }        log.info("count之后count值:{}",count);        // 这里是一个小技巧，咱们依据count中元素呈现的次数计算对应元素第一次应该呈现在output中的下标。        //这里的下标是从右往左数的        for (int i=1; i<10; i++) {            count[i] += count[i - 1];        }        log.info("整顿count对应的output下标:{}",count);        // 依据count中的下标，构建排序后的数组        //插入一个之后，相应的count下标要减一        for (int i = n-1; 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<n; ++i)            array[i] = output[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);        //拿到数组的最大值，用于计算digit        int 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)。

本文的代码地址：

learn-algorithm

本文已收录于 http://www.flydean.com/algorithm-radix-sort/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」,懂技术，更懂你！