web开发中基数排序是什么意思

这篇文章主要介绍了web开发中基数排序是什么意思,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。

创新互联建站专注于洛浦网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供洛浦营销型网站建设,洛浦网站制作、洛浦网页设计、洛浦网站官网定制、小程序开发服务,打造洛浦网络公司原创品牌,更为您提供洛浦网站排名全网营销落地服务。

基数排序的例子

什么是基数排序呢?

考虑一下,虽然我们不能直接将所有范围内的数字都使用count数组进行排序,但是我们可以考虑按数字的位数来进行n轮count排序,每一轮都只对数字的某一位进行排序。

最终仍然可以得到结果,并且还可以摆脱count数组大小的限制,这就是基数排序。

假如我们现在数组的元素是:1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793。

先看动画,看下最直观的基数排序的过程:

web开发中基数排序是什么意思

在上面的例子中,我们先对个位进行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; 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

跟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);//拿到数组的最大值,用于计算digitint 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)。

感谢你能够认真阅读完这篇文章,希望小编分享的“web开发中基数排序是什么意思”这篇文章对大家有帮助,同时也希望大家多多支持创新互联,关注创新互联行业资讯频道,更多相关知识等着你来学习!


分享标题:web开发中基数排序是什么意思
文章分享:http://myzitong.com/article/pdigjo.html