鸽巢排序

鸽巢排序

分類	排序算法
數據結構	數組
最差時間復雜度	$O(N+n)$, where N is the range of key values and n is the input size
最差空間復雜度	$O(N+n)$
最佳算法	If and only if $N=O(n)$

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

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

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

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

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

算法

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

 function pigeonhole_sort(array a[n])
      array b[N]
      var i,j
      
      zero_var (b)      (* Zero out array b *)
      
      for i in [0...length(a)-1]
          b[a[i]] := b[a[i]]+1
   
      (* 把结果复制回数组a *)
      j := 0
      for i in [0...length(b)-1]
          repeat b[i] times
             a[j] := i
             j := j+1