查看“︁鸽巢排序”︁的源代码

{{Onesource|time=2020-04-05T09:39:54+00:00}}
{{NoteTA
|G1 = IT
}}
{{Infobox Algorithm
|class=[[排序算法]]
|image=
|data=[[數組]]
|time=<math>O(N+n)</math>
|best-time=<math> O(n) </math>
|space=<math>O(N+n)</math>
|Other=当且仅当<math>N=O(n)</math>时算法取得最优时间复杂度
|Var1=n
|Def1=数组长度
|Var2=N
|Def2=最大值减最小值
}} 

'''鸽巢排序'''（{{lang-en|Pigeonhole sort}}），也被称作'''基数分类'''，是一种[[时间复杂度]]为<math> O(n) </math>（[[大O符號]]）且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法。但它只有在差值（或者可被映射在差值）很小的范围内的数值排序的情况下实用<ref>{{Cite web|url=https://xlinux.nist.gov/dads/HTML/pigeonholeSort.html|title=NIST's Dictionary of Algorithms and Data Structures: pigeonhole sort|date=2019-02-11|access-date=2020-04-05|archive-date=2019-05-28|archive-url=https://web.archive.org/web/20190528041750/https://xlinux.nist.gov/dads/HTML/pigeonholeSort.html|dead-url=no}}</ref>。

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

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

鸽巢排序的一个比较有名的变形是'''吻合排序法'''（{{lang|en|tally sort}}），它仅仅适用非常有限的题目，这个算法因在''[[Jon Bentley|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 ===
<syntaxhighlight lang=python>
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])
</syntaxhighlight>

==参考文献==
{{reflist}}
{{-}}
{{排序算法表}}
{{算法}}
[[Category:排序算法]]

[[ru:Сортировка подсчётом#Алгоритм со списком]]