鴿巢排序

鴿巢排序（Pigeonhole sort），也被稱作基數分類，是一種時間複雜度為O(n)（大O符號）且在不可避免遍歷每一個元素並且排序的情況下效率最好的一種排序算法。但它只有在差值（或者可被映射在差值）很小的範圍內的數值排序的情況下實用。

當涉及到多個不相等的元素，且將這些元素放在同一個"鴿巢"的時候，算法的效率會有所降低。為了簡便和保持鴿巢排序在適應不同的情況，比如兩個在同一個存儲桶中結束的元素必然相等

我們一般很少使用鴿巢排序，因為它很少可以在靈活性，簡便性，尤是速度上超過其他排序算法。事實上，桶排序較鴿巢排序更加的實用。

基本介紹

• 中文名：鴿巢排序
• 外文名：Pigeonhole sort
• 別名：基數分類
• 屬性：一種排序算法

鴿巢排序(Pigeonhole sort)

鴿巢排序, 也被稱作基數分類, 是一種時間複雜度為(Θ(n))且在不可避免遍歷每一個元素並且排序的情況下效率最好的一種排序算法. 但它只有在差值(或者可被映射在差值)很小的範圍內的數值排序的情況下實用.

當涉及到多個不相等的元素, 且將這些元素放在同一個"鴿巢"的時候, 算法的效率會有所降低.為了簡便和保持鴿巢排序在適應不同的情況, 比如兩個在同一個存儲桶中結束的元素必然相等

我們一般很少使用鴿巢排序, 因為它很少可以在靈活性, 簡便性, 尤是速度上超過其他排序算法. 事實上, 桶排序較鴿巢排序更加的實用.

鴿巢排序的一個比較有名的變形是tally sort, 它僅僅適用非常有限的題目, 這個算法因在Programming Pearls一書中作為解決一個非常規有限集問題方法的例子而著名.

顯然, 快速排序可以當作只有兩個(有些情況下是三個)"鴿巢"的鴿巢排序。

算法效率

最壞時間複雜度： O(N+n)

最好時間複雜度：O(N+n)

平均時間複雜度： O(N+n)

最壞空間複雜度：O(N*n)

算法分析

1. 給定一個待排序數組，創建一個備用數組（鴿巢），並初始化元素為0，備用數組的索引即是待排序數組的值。

2.遍歷待排序數組，備用數組（鴿巢）存放索引值得個數。

3.遍歷備用數組（鴿巢），將排序值放回原數組得到排序後的數組的值。

算法代碼

算法偽代碼(類似Python代碼格式)

def pigeonhole_sort ( array a[n] ) :array auxiliary[N] = {0}var i ,kvar j = 0for i = 0 -> nauxiliary[ a[i] ] ++for i = 0 -> Nfor k = 0 ->auxiliary[i]a[j++] = i

C源碼

函式功能：實現鴿巢排序。參數： *array 為需要排序的數組，length為數組長度。NUM 可以為全局變數 為待排序數組中最大的元素值。

void pigeonhole_sort(int* array, int length) 　{int auxiliary[NUM] = {0};int i, k,j = 0;for(i = 0; i < length; ++i)auxiliary[array[i]]++;for(i = 0; i < NUM; ++i)for(k = 0; k < auxiliary[i]; ++k)array[j++] = i;}