from -> introdution to algorithms
原理简单，稳定性高，有应用条件 即 ： n个输入元素都是在0 - k之间的整数，当k = O(n)时, 计数排序的时间为O(n).
#include <stdio.h>
#include <string.h>
const int _ = 0x7fffffff;
int a[100], n, out[100];
int c[100];
int main(){
freopen("count_sort.in", "r", stdin);
freopen("count_sort.out", "w", stdout);
int i, k;
while(scanf("%d", &n) != -1){
k = -_;
memset(c, 0, sizeof(c));
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
if(a[i] > k)k = a[i];
c[a[i]]++; //初始化<=自己的元素个数为1。
}
for(i = 1; i <= k; i++)c[i] += c[i - 1];//c中存放整个数列中小于等于自己的元素的个数。
for(i = 0; i < n; i++){
out[c[a[i]]] = a[i];//放到相应的位置上 比如 有 5个元素小于等于自己(包含自己)，那么，这个元素应该排在第五位
c[a[i]]--;//计数器 - 1
}
for(i = 1; i <= n; i++)printf("%d ", out[i]);
puts("");
}
return 0;
}