写点什么

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

发布于: 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
用户头像

关注公众号:程序那些事,更多精彩等着你! 2020.06.07 加入

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

评论

发布
暂无评论
看动画学算法之:排序-基数排序