计算机科学

首页 > 计算机科学

鸽巢排序

2018-08-28 09:43:05     所属分类:排序算法
鸽巢排序
分类 排序算法
数据结构 数组
最坏时间复杂度 (n是数组长度,N是最大值减最小值)
最坏空间复杂度

鸽巢排序(Pigeonhole sort),也被称作基数分类,是一种时间复杂度为(大O符号)且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法。但它只有在差值(或者可被映射在差值)很小的范围内的数值排序的情况下实用。

当涉及到多个不相等的元素,且将这些元素放在同一个"鸽巢"的时候,算法的效率会有所降低。为了简便和保持鸽巢排序在适应不同的情况,比如两个在同一个存储桶中结束的元素必然相等

我们一般很少使用鸽巢排序,因为它很少可以在灵活性,简便性,尤是速度上超过其他排序算法。事实上,桶排序较鸽巢排序更加的实用。

鸽巢排序的一个比较有名的变形是tally sort,它仅仅适用非常有限的题目,这个算法因在Programming Pearls一书中作为解决一个非常规有限集问题方法的例子而著名。

显然,快速排序可以当作只有两个(有些情况下是三个)"鸽巢"的鸽巢排序

算法

对于N个不同元素的鸽巢排序算法(伪代码)

 function pigeonhole_sort(array an)
      array bN
      var i,j
      
      zero_var (b)      (* Zero out array b *)
      
      for i in 0...length(a)-1
          bai := bai+1
   
      (* 把结果复制回数组a *)
      j := 0
      for i in 0...length(b)-1
          repeat bi times
             aj := i
             j := j+1
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/339836.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


上一篇:选择排序
下一篇:插入排序
相关推荐
爱淘宝