鸽巢排序

鸽巢排序
概况
类别	排序算法
数据结构	数组
复杂度
最坏时间复杂度
最优时间复杂度
空间复杂度
其他
	当且仅当时算法获取最优时间复杂度
相关变量的定义
n	数组长度
N	最大值减最小值

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

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

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

鸽巢排序的一个比较有名的变形是吻合排序法（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

程序实现

Python 3.10

def pigeonhole_sort(arr: list) -> list:
    pigeonhole_len: int = 0
    pigeonhole: list = [0]
    for i in arr:
        if pigeonhole_len < i:
            pigeonhole += [0] * (i - pigeonhole_len) 
            pigeonhole_len = i
        pigeonhole[i] += 1

    results: list = []
    for i, v in enumerate(pigeonhole):
        results += [i] * v
    return results

if __name__ == "__main__":
    pigeonhole_sort([1, 2, 100, 3, 8, 3, 9, 0, 0, 1])

参考文献

^ NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort. 2019-02-11 [2020-04-05]. （原始内容存档于2019-05-28）.

[1] NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort. 2019-02-11 [2020-04-05]. （原始内容存档于2019-05-28）.

[1]