鸽巢排序 鸽巢排序英語Pigeonhole sort也被称作基数分类是一种时间复杂度为 O  n  displaystyle On 大O符號且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法但它只有在差值或者可被映射在差值很小的范围内的数值排序的情况下实用 当涉及到多个不相等的元素且将这些元素放在同一个鸽巢的时候算法的效率会有所降低为了简便和保持鸽巢排序在适应不同的情况比如两个在同一个存储桶中结束的元素必然相等 我们一般很少使用鸽巢排序因为它很少可以在灵活性简便性尤是速度上超过其他排序算法事实上桶排序较鸽巢排序更加的实用 鸽巢排序的一个比较有名的变形是吻合排序法tally sort它仅仅适用非常有限的题目这个算法因在Programming Pearls一书中作为解决一个非常规有限集问题方法的例子而著名 显然快速排序可以当作只有两个有些情况下是三个鸽巢的鸽巢排序