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


这篇文章主要介绍了web开发中基数排序是什么意思,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。什么是基数排序呢?考虑一下,虽然我们不能直接将所有范围内的数字都使用count数组进行排序,但是我们可以考虑按数字的位数来进行n轮count排序,每一轮都只对数字的某一位进行排序。最终仍然可以得到结果,并且还可以摆脱count数组大小的限制,这就是基数排序。假如我们现在数组的元素是:1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793。先看动画,看下最直观的基数排序的过程:在上面的例子中,我们先对个位进行count排序,然后对十位进行count排序,然后是百位和千位。最后生成最终的排序结果。因为基数排序实际上是分别按位数的count排序。所以我们可以重用之前写的count排序的代码,只是需要进行一些改造。doCountingSort方法除了传入数组外,还需要传入排序的位数digit,我们用1,10,100,1000来表示。看一下改造过后的doCountingSort方法:跟count排序变化不大,区别就是这里我们需要使用count[(array[i]/digit)%10],来对每一位进行排序。另外,为了计算出位数digit的值,我们还需要拿到数组中最大元素的值:看下怎么调用:看下输出结果:很好,结果都排序了。从计算过程我们可以看出,基数排序的时间复杂度是O(d*(n+b)) ,其中b是数字的进制数,比如上面我们使用的是10进制,那么b=10。d是需要循环的轮数,也就是数组中最大数的位数。假如数组中最大的数字用K表示,那么d=logb(k)。综上,基数排序的时间复杂度是O((n+b) * log开发云主机域名b(k))。当k
考虑下当b=n的情况下,基数排序的时间复杂度可以近似等于线性时间复杂度O(n)。感谢你能够认真阅读完这篇文章,希望小编分享的“web开发中基数排序是什么意思”这篇文章对大家有帮助,同时也希望大家多多支持开发云,关注开发云行业资讯频道,更多相关知识等着你来学习!

相关推荐: 虚拟主机如何开通

这篇文章运用简单易懂的例子给大家介绍虚拟主机如何开通,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。1.正规服务商购买虚拟主机,一定要选择正规的主机服务商。否则购买没有资质的虚拟主机,稳定性和安全性没有保障,开发云主机域名严重影响网站后期的…

免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 05/16 09:32
下一篇 05/16 09:32

相关推荐