看动画学算法之:排序-基数排序
简介
之前的文章我们讲了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)。
本文的代码地址:
本文已收录于 http://www.flydean.com/algorithm-radix-sort/
最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!
欢迎关注我的公众号:「程序那些事」,懂技术,更懂你!
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
java安全编码指南之:可见性和原子性
简介 java类中会定义很多变量,有类变量也有实例变量,这些变量在访问的过程中,会遇到一些可见性和原子性的问题。这里我们来详细了解一下怎么避免这些问题。 不可变对象的可见性 不可变对象就是初始化之后不能够被修改的对象,那么是不是类中引入了不可变对象,所有对不可变对象的修改都立马对所有线程可见呢? 实际上,不可变对象只能保证在多线程环境中,对象使用的安全性,并不能够保证对象的可见性。 先来讨论一下可变性,我们考虑下面的一个例子: public final class ImmutableObject { private final int age; public ImmutableObject(int age){ this.age=age; } } 我们定义了一个ImmutableObject对象,class是final的,并且里面的唯一字段也是final的。所以这个ImmutableObject初始化之后就不能够改变。 然后我们定义一个类来get和set这个ImmutableObject: public class ObjectWithNothing { private Immutabl...
- 下一篇
java安全编码指南之:异常处理
简介 异常是java程序员无法避免的一个话题,我们会有JVM自己的异常也有应用程序的异常,对于不同的异常,我们的处理原则是不是一样的呢? 一起来看看吧。 异常简介 先上个图,看一下常见的几个异常类型。 所有的异常都来自于Throwable。Throwable有两个子类,Error和Exception。 Error通常表示的是严重错误,这些错误是不建议被catch的。 注意这里有一个例外,比如ThreadDeath也是继承自Error,但是它表示的是线程的死亡,虽然不是严重的异常,但是因为应用程序通常不会对这种异常进行catch,所以也归类到Error中。 Exception表示的是应用程序希望catch住的异常。 在Exception中有一个很特别的异常叫做RuntimeException。RuntimeException叫做运行时异常,是不需要被显示catch住的,所以也叫做unchecked Exception。而其他非RuntimeException的Exception则需要显示try catch,所以也叫做checked Exception。 不要忽略checked excep...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS关闭SELinux安全模块
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- Hadoop3单机部署,实现最简伪集群
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS6,CentOS7官方镜像安装Oracle11G
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS8编译安装MySQL8.0.19
- CentOS6,7,8上安装Nginx,支持https2.0的开启