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

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

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

Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements (n) and the number of possible key values (N) are approximately the same. It requires O(n + N) time. It is similar to counting sort, but differs in that it "moves items twice: once to the bucket array and again to the final destination [whereas] counting sort builds an auxiliary array then uses the array to compute each item's final destination and move the item there."