加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

分配排序以及桶排序及基数排序

(2013-08-27 22:48:34)
标签:

分配排序

桶排序

基数排序

it

分类: 数据结构

桶排序

桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。

桶排序以下列程序进行:

设置一个定量的数组当作空桶子。

寻访串行,并且把项目一个一个放到对应的桶子去。

对每个不是空的桶子进行排序。

从不是空的桶子里把项目再放回原来的串行中。

伪代码

function bucket-sort(array, n) is

  buckets ← new array of n empty lists

  for i = 0 to (length(array)-1) do

    insert array[i] into buckets[msbits(array[i], k)]

  for i = 0 to n - 1 do

    next-sort(buckets[i])

  return the concatenation of buckets[0], ..., buckets[n-1]

基数排序

基数排序英语:Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

它是这样实现的:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。

效率

基数排序的时间复杂度是 O(k•n),其中n是排序元素个数,k是数字位数。注意这不是说这个时间复杂度一定优于O(n·log(n)),因为k的大小一般会受到 n 的影响。 以排序n个不同整数来举例,假定这些整数以B为底,这样每位数都有B个不同的数字,k就一定不小于logB(n)。由于有B个不同的数字,所以就需要B个不同的桶,在每一轮比较的时候都需要平均n·log2(B) 次比较来把整数放到合适的桶中去,所以就有:

大于或等于 logB(n)

每一轮(平均)需要 n·log2(B) 次比较

所以,基数排序的平均时间T就是:

≥ logB(n)·n·log2(B) = log2(n)·logB(2)·n·log2(B) = log2(n)·n·logB(2)·log2(B) = n·log2(n)

所以和比较排序相似,基数排序需要的比较次数:T ≥ n·log2(n)。 故其时间复杂度为 Ω(n·log2(n)) = Ω(n·log n) 

 C++算法分析

分配排序以及桶排序及基数排序

分配排序以及桶排序及基数排序

分配排序以及桶排序及基数排序

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:归并排序
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇归并排序
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有