鴿巢排序

鴿巢排序（英語：Pigeonhole sort），也被稱作基數分類，是一種時間複雜度為$O(n)$（大O符號）且在不可避免遍歷每一個元素並且排序的情況下效率最好的一種排序算法。但它只有在差值（或者可被映射在差值）很小的範圍內的數值排序的情況下實用。

鴿巢排序
概況
類別	排序算法
資料結構	數組
複雜度
最壞時間複雜度	$O(N+n)$
最優時間複雜度	$O(n)$
空間複雜度	$O(N+n)$
其他
當且僅當$N=O(n)$時算法取得最優時間複雜度
相關變量的定義
n	數組長度
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

程式實現

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])