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)