【算法导论】C++实现计数排序

计数排序的基本思想为：对每一个输入的元素x，确定出小于x的元素的个数。有了这一信息，那么就可以把x直接放到相应的位置上。

特点：

1 需要临时的存储空间，如果排序数据范围特别大时，空间开销很大。

2 适合于排序0 - 100以内的数据。

3 排序的时间复杂度为O(n)。

1. #include <iostream>  
2. #include <string>  
3.  
4. const int size = 100; 
5. int * array_list; 
6. int * array_list_a; 
7. void print_list(int * ,int ); 
8. void count_sort(int * ,int * ,int ); 
9.  
10. int main(int argc,char * argv[]) 
11. { 
12.      
13.     array_list = new int [sizeof(int)*size]; 
14.     array_list_a = new int [sizeof(int)*size]; 
15.     srand(0); 
16.     for(int i=0;i<size;i++) 
17.     {/*随机的填充数组元素*/ 
18.         int ran_num=rand()% size; 
19.         array_list[i] = ran_num; 
20.     } 
21.     print_list(array_list,size); 
22.     count_sort(array_list, array_list_a, size); 
23.     print_list(array_list_a,size); 
24.     delete array_list; 
25.     delete array_list_a; 
26.     return 0; 
27. } 
28. /*假设输入的数据都是介于0 - k 的数*/ 
29. void count_sort(int * array_list_a,int * array_list_b,int k) 
30. { 
31.     int * c = new int [sizeof(int) * k]; 
32.     for(int i=0;i<k;i++) 
33.     {/*初始化临时数组*/ 
34.         c[i] = 0; 
35.     } 
36.     for(int i=0;i<size;i++) 
37.     {/*对于输入数组的重复的数值进行统计，在临时数组c的相应的位置予以记录*/ 
38.         c[array_list_a[i]] += 1;   
39.     } 
40.     for(int i=1;i<k;i++) 
41.     {/*小于当前数据元素的个数*/ 
42.         c[i] += c[i-1]; 
43.     } 
44.     for(int j=size-1;j>=0;j--) 
45.     { 
46.         array_list_b[c[array_list_a[j]] - 1] = array_list_a[j]; 
47.         c[array_list_a[j]] -= 1; 
48.     } 
49.     delete c; 
50. } 
51. void print_list(int * array_list,int length) 
52. { 
53.     for(int i=0;i<length;i++) 
54.     { 
55.         std::cout<<array_list[i]<<"\t"; 
56.     } 
57.     std::cout<<std::endl; 
58. }