计数排序

核心代码

 1 void CountSort(int arr[], int len)
 2 {
 3     int i;
 4     int j;
 5     int nMin;
 6     int nMax;
 7     int *pCount = NULL;
 8 
 9     assert(arr!=NULL && len>0);
10 
11     nMin = arr[0];
12     nMax = arr[0];
13     for(i=0; i<len; ++i)
14     {
15         //找最大值
16         if(arr[i] > nMax)
17         {
18             nMax = arr[i];
19         }
20         //找最小值
21         if(arr[i] < nMin)
22         {
23             nMin = arr[i];
24         }
25     }
26 
27     //开辟计数数组
28     pCount = (int *)malloc(sizeof(int)*(nMax-nMin+1));
29 
30     //数组清空
31     memset(pCount, 0, sizeof(int)*(nMax-nMin+1));
32 
33     //计数
34     for(i=0; i<len; ++i)
35     {
36         ++pCount[arr[i]-nMin];
37     }
38 
39     //排序
40     j = 0;
41     for(i=0; i<nMax-nMin+1; ++i)
42     {
43         while(pCount[i])
44         {
45             arr[j] = i+nMin;
46             --pCount[i];
47             ++j;
48         }
49     }
50 
51     //释放计数数组
52     free(pCount);
53     pCount = NULL;
54 }

应用场合：排序的数据属于同一个范围之内，分配得非常密集，并且重复的次数很多。

算法分析：

　　最好时间复杂度：O(n)

　　平均时间复杂度：O(n)

　　最坏时间复杂度：O(n)

　　　　空间复杂度：O(n)

　　　　　　稳定性：不稳定