鴿巢排序

鴿巢排序
概況
類別	排序演算法
資料結構	數組
複雜度
最壞時間複雜度	$O(N+n)$
最佳時間複雜度	$O(n)$
空間複雜度	$O(N+n)$
其他
若且唯若$N=O(n)$時演算法取得最佳時間複雜度
相關變數的定義
n	陣列長度
N	最大值減最小值

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

當涉及到多個不相等的元素，且將這些元素放在同一個「鴿巢」的時候，演算法的效率會有所降低。為了簡便和保持鴿巢排序在適應不同的情況，比如兩個在同一個儲存桶中結束的元素必然相等。

我們一般很少使用鴿巢排序，因為它很少可以在靈活性、簡便性、尤是速度上超過其他排序演算法。事實上，桶排序較鴿巢排序更加的實用。

鴿巢排序的一個比較有名的變形是吻合排序法（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])