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

程序那些事

关注

发布于: 2020 年 09 月 27 日

简介

之前的文章我们讲了 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/
最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！
欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！

发布于: 2020 年 09 月 27 日阅读数: 47

原文链接:【http://xie.infoq.cn/article/16792685d22196abecf5face8】。文章转载请联系作者。

程序那些事

关注

关注公众号：程序那些事，更多精彩等着你！ 2020.06.07 加入

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧，尽在公众号：程序那些事！

发布

暂无评论

创作场景

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

简介

基数排序的例子

基数排序的 java 代码实现

基数排序的时间复杂度

程序那些事

评论