Pigeonhole 排序基本資訊

Pigeonhole Sort 是一種排序演算法，適用於排序元素列表，其中元素的數量（n）和可能的鍵值（N）的數量大致相同。它需要 O（n + Range）時間，其中 n 是輸入陣列中元素的數量，‘Range’是陣列中可能值的數量。

Pigeonhole 排序的工作（虛擬碼）：

1. 在陣列中查詢最小值和最大值。設最小值和最大值分別為 min 和 max。同時找到範圍’max-min-1’。
2. 設定一個最初為空的鴿籠陣列，其大小與射程相同。
3. 訪問陣列的每個元素，然後將每個元素放入其鴿籠中。元素 input [i]被放入索引輸入[i] - min 的孔中。
4. 按順序在整個 pigeonhole 陣列中啟動迴圈，並將非空洞中的元素放回原始陣列中。

Pigeonhole 排序類似於計數排序，因此這裡是 Pigeonhole 排序和計數排序之間的比較。

http://i.stack.imgur.com/37SDY.jpg

Pigeonhole 排序示例：

http://i.stack.imgur.com/VKhzI.jpg

空間輔助： O(n)
時間複雜度： O(n + N)