【算法導論】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. }