计数排序是一个类似于桶排序的排序算法，其优势是对已知数量范围的数组进行排序。它创建一个长度为这个数据范围的数组C，C中每个元素记录要排序数组中对应记录的出现个数。这个算法于1954年由 Harold H. Seward 提出。
它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。
这个算法是为了学习后缀数组才看的，刚看到的时候，觉得这个算法有点、、、后来想想，当初一个这个算法的题，可是想了一个多星期啊（当时什么排序只会冒泡，连计数排序的思想都没的、、），题目是这样的：给你 0 - 100 之内的1000000个数，叫你排序之后输出、、、
我们先设一个数组 t ， t [7] = { 1, 3, 1, 2 , 5, 1, 1} ; 再取一个最大的值作为计数数组的最大范围，这里最大值是 5， 所以计数后， cnt[1] = 4, cnt[2] = 1, cnt[3] = 1; cnt[4] = 0; cnt[5] = 1; 思想比较简单、、于是就愤怒地贴上了代码，如下：
int Sort(int *t, int *cnt, int n, int k)
{
int idx = 0;
for (int i = 0; i < n; i++)
{
cnt[t[i]] ++;
}
for (int i = 0; i < k; i++)
{
while (cnt[i]-- > 0)
{
[idx++] = i;
}
}
}
// t[] 表示需要排序的数组， n 表示t[] 的大小， cnt 表示计数的数组， k 表示t[] 中最大的数
看到一篇博客（链接）上有做过比较，0 - 100 之内的1000000个 随机数排序，计数排序 比 快速排序 快 6 倍
，所谓每种算法都有各自的优势嘛，每个人、、也是、、
应用：
优化前向星
前向星不需要像邻接表那样用指针指向下一条边，还是挺方便的。但是，由于前向星初始化需要快排一遍，相对邻接表要慢许多。考虑到一般图论题点数都不会很大，所以可以改为采用计数排序的思想对前向星进行排序。
一开始读入时，先算出每个点出去的边有多少条，然后计算出排序后每个点出去的第一条边位置应在哪里，最后把全部边扫一遍放到排序后应在的位置就好了。
这样排序的话初始化的时间复杂度就降到了O(m)，总体时间并不会逊色于邻接表。
优化后缀数组的倍增算法
如果用快速排序，该算法的复杂度为O(nlog^2n)。改用计数排序后，复杂度降为O(nlogn)。