計數(shù)排序，漢語拼音：ji shu pai xu。它是一個非基于比較的排序算法，該算法于1954年由 Harold H. Seward 提出。它的優(yōu)勢在于在對一定范圍內的整數(shù)排序時，它的復雜度為Ο(n+k)（其中k是整數(shù)的范圍），快于任何比較排序算法。當然這是一種犧牲空間換取時間的做法，而且當O(k)>O(n*log(n))的時候其效率反而不如基于比較的排序（基于比較的排序的時間復雜度在理論上的下限是O(n*log(n)), 如歸并排序，堆排序）
算法思想
計數(shù)排序對輸入的數(shù)據(jù)有附加的限制條件：
1、輸入的線性表的元素屬于有限偏序集S；
2、設輸入的線性表的長度為n，|S|=k（表示集合S中元素的總數(shù)目為k），則k=O(n)。
在這兩個條件下，計數(shù)排序的復雜性為O(n)。
計數(shù)排序的基本思想是對于給定的輸入序列中的每一個元素x，確定該序列中值小于x的元素的個數(shù)（此處并非比較各元素的大小，而是通過對元素值的計數(shù)和計數(shù)值的累加來確定）。一旦有了這個信息，就可以將x直接存放到最終的輸出序列的正確位置上。例如，如果輸入序列中只有17個元素的值小于x的值，則x可以直接存放在輸出序列的第18個位置上。當然，如果有多個元素具有相同的值時，我們不能將這些元素放在輸出序列的同一個位置上，因此，上述方案還要作適當?shù)男薷摹?/p>
算法過程
假設輸入的線性表L的長度為n，L=L1,L2,..,Ln；線性表的元素屬于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；則計數(shù)排序可以描述如下：
1、掃描整個集合S，對每一個Si∈S，找到在線性表L中小于等于Si的元素的個數(shù)T(Si)；
2、掃描整個線性表L，對L中的每一個元素Li，將Li放在輸出線性表的第T(Li)個位置上，并將T(Li)減1。
算法描述
PASCAL語言描述
C++語言描述
c語言實現(xiàn)
JAVA語言描述
C#語言描述
Python語言實現(xiàn)
GO語言實現(xiàn)
總結
我們看到，計數(shù)排序算法沒有用到元素間的比較，它利用元素的實際值來確定它們在輸出數(shù)組中的位置。因此，計數(shù)排序算法不是一個基于比較的排序算法，從而它的計算時間下界不再是O(nlogn)。另一方面，計數(shù)排序算法之所以能取得線性計算時間的上界是因為對元素的取值范圍作了一定限制，即k=O(n)。如果k=n2,n3,..，就得不到線性時間的上界。此外，我們還看到，由于算法第4行使用了downto語句，經(jīng)計數(shù)排序，輸出序列中值相同的元素之間的相對次序與他們在輸入序列中的相對次序相同，換句話說，計數(shù)排序算法是一個穩(wěn)定的排序算法。
應用
優(yōu)化前向星
前向星不需要像鄰接表那樣用指針指向下一條邊，還是挺方便的。但是，由于前向星初始化需要快排一遍，相對鄰接表要慢許多。考慮到一般圖論題點數(shù)都不會很大，所以可以改為采用計數(shù)排序的思想對前向星進行排序。
一開始讀入時，先算出每個點出去的邊有多少條，然后計算出排序后每個點出去的第一條邊位置應在哪里，最后把全部邊掃一遍放到排序后應在的位置就好了。
這樣排序的話初始化的時間復雜度就降到了O(m)，總體時間并不會遜色于鄰接表。
優(yōu)化后綴數(shù)組的倍增算法
如果用快速排序，該算法的復雜度為O(nlog^2n)。改用計數(shù)排序后，復雜度降為O(nlogn)。
參考資料 >