算法思想
計數排序對輸入的數據有附加的限制條件：
1、輸入的線性表的元素屬於有限偏序集S；
2、設輸入的線性表的長度為n，|S|=k（表示集合S中元素的總數目為k），則k=O(n)。
在這兩個條件下，計數排序的複雜性為O(n)。
計數排序的基本思想是對於給定的輸入序列中的每一個元素x，確定該序列中值小於x的元素的個數（此處並非比較各元素的大小，而是通過對元素值的計數和計數值的累加來確定）。一旦有了這個信息，就可以將x直接存放到最終的輸出序列的正確位置上。例如，如果輸入序列中只有17個元素的值小於x的值，則x可以直接存放在輸出序列的第18個位置上。當然，如果有多個元素具有相同的值時，我們不能將這些元素放在輸出序列的同一個位置上，因此，上述方案還要作適當的修改。
算法過程
假設輸入的線性表L的長度為n，L=L1,L2,..,Ln；線性表的元素屬於有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；則計數排序可以描述如下：
1、掃描整個集合S，對每一個Si∈S，找到線上性表L中小於等於Si的元素的個數T(Si)；
2、掃描整個線性表L，對L中的每一個元素Li，將Li放在輸出線性表的第T(Li)個位置上，並將T(Li)減1。
算法描述
PASCAL語言描述
C++語言描述
C語言實現
JAVA語言描述
C#語言描述
python語言實現
GO語言實現
總結
我們看到，計數排序算法沒有用到元素間的比較，它利用元素的實際值來確定它們在輸出數組中的位置。因此，計數排序算法不是一個基於比較的排序算法，從而它的計算時間下界不再是O(nlogn)。另一方面，計數排序算法之所以能取得線性計算時間的上界是因為對元素的取值範圍作了一定限制，即k=O(n)。如果k=n2,n3,..，就得不到線性時間的上界。此外，我們還看到，由於算法第4行使用了downto語句，經計數排序，輸出序列中值相同的元素之間的相對次序與他們在輸入序列中的相對次序相同，換句話說，計數排序算法是一個穩定的排序算法。
套用
最佳化前向星
前向星不需要像鄰接表那樣用指針指向下一條邊，還是挺方便的。但是，由於前向星初始化需要快排一遍，相對鄰接表要慢許多。考慮到一般圖論題點數都不會很大，所以可以改為採用計數排序的思想對前向星進行排序。
一開始讀入時，先算出每個點出去的邊有多少條，然後計算出排序後每個點出去的第一條邊位置應在哪裡，最後把全部邊掃一遍放到排序後應在的位置就好了。
這樣排序的話初始化的時間複雜度就降到了O(m)，總體時間並不會遜色於鄰接表。
最佳化後綴數組的倍增算法
如果用快速排序，該算法的複雜度為O(nlog^2n)。改用計數排序後，複雜度降為O(nlogn)。
