[科普中國]-鴿巢排序

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

當(dāng)涉及到多個(gè)不相等的元素，且將這些元素放在同一個(gè)"鴿巢"的時(shí)候，算法的效率會(huì)有所降低。為了簡便和保持鴿巢排序在適應(yīng)不同的情況，比如兩個(gè)在同一個(gè)存儲(chǔ)桶中結(jié)束的元素必然相等

我們一般很少使用鴿巢排序，因?yàn)樗苌倏梢栽陟`活性，簡便性，尤是速度上超過其他排序算法。事實(shí)上，桶排序較鴿巢排序更加的實(shí)用。

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

當(dāng)涉及到多個(gè)不相等的元素, 且將這些元素放在同一個(gè)"鴿巢"的時(shí)候, 算法的效率會(huì)有所降低.為了簡便和保持鴿巢排序在適應(yīng)不同的情況, 比如兩個(gè)在同一個(gè)存儲(chǔ)桶中結(jié)束的元素必然相等

我們一般很少使用鴿巢排序, 因?yàn)樗苌倏梢栽陟`活性, 簡便性, 尤是速度上超過其他排序算法. 事實(shí)上, 桶排序較鴿巢排序更加的實(shí)用.

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

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

算法效率最壞時(shí)間復(fù)雜度： O(N+n)

最好時(shí)間復(fù)雜度：O(N+n)

平均時(shí)間復(fù)雜度： O(N+n)

最壞空間復(fù)雜度：O(N*n)1

算法分析1. 給定一個(gè)待排序數(shù)組，創(chuàng)建一個(gè)備用數(shù)組（鴿巢），并初始化元素為0，備用數(shù)組的索引即是待排序數(shù)組的值。

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

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

算法代碼算法偽代碼(類似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++] = iC源碼函數(shù)功能：實(shí)現(xiàn)鴿巢排序。參數(shù)： *array 為需要排序的數(shù)組，length為數(shù)組長度。NUM 可以為全局變量 為待排序數(shù)組中最大的元素值。void pigeonhole_sort(int* array, int length) {int auxiliary[NUM] = {0};int i, k,j = 0;for(i = 0; i