计数排序

浏览数：18 / 时间：2015年06月08日

 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 }