【算法導論】C++實現計數排序

計數排序的基本思想為：對每一個輸入的元素x，確定出小於x的元素的個數。有了這一信息，那麼就可以把x直接放到相應的位置上。

特點：

1 需要臨時的存儲空間，如果排序數據范圍特別大時，空間開銷很大。

2 適合於排序0 - 100以內的數據。

3 排序的時間復雜度為O(n)。

1. #include <iostream>
2. #include <string>
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 );
10. int main(int argc,char * argv[])
11. {
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. }