1 //计数排序的思想是这样的,如果小于等于a的数字有n个,那么就把a放在第n+1个位置,从而达到排序的目的
2 //关键是怎么统计小于等于a的数字有多少个,
3 /*
4 可以采用这样一个办法,将数组元素的值映射为下标,统计该下标出现了多少次,然后再统计比该下标小或者等的下标出现了多少次,
5 从而就统计出了小于等于a的数字有多少个
6 */
7
8 //计数排序的时间复杂度为O(n), 但是缺点为数据有多大,数据就要开多大。
9 #include <stdio.h>
10 #include <string.h>
11 const int N = 1000;
12 int a[N],b[N];
13 int c[1000000];
14
15
16 void countingSort(int n, int m)
17 {
18 int i;
19 for(i=0; i<=m; ++i) c[i] = 0;
20 for(i=0; i<n; ++i) c[a[i]] ++;//将a[i] 映射为下标,统计该下标出现了多少次
21 for(i=1; i<=m; ++i) c[i] += c[i-1];//统计比该小或者等的下标出现了多少次
22 //for(i=n-1; i>=0; --i) //稳定
23 for(i=0; i<n; ++i)//不稳定
24 b[--c[a[i]]] = a[i];//c[]记录了小于等于a[i]的数字有多少个,直接将a[i]放在相应的位置上去
25 }
26 int main()
27 {
28 int n,m,i;
29 scanf("%d",&n);
30 m = -1;
31 for(i=0; i<n; ++i)
32 {
33 scanf("%d",&a[i]);
34 m = a[i] > m ? a[i] : m;
35 }
36 countingSort(n, m);
37 for(i=0; i<n; ++i)
38 printf("%d ",b[i]);
39
40 return 0;
41 }