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

frankwtq 2012-10-15

计数排序的基本思想为:对每一个输入的元素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.     array_list = new int [sizeof(int)*size]; 
  13.     array_list_a = new int [sizeof(int)*size]; 
  14.     srand(0); 
  15.     for(int i=0;i<size;i++) 
  16.     {/*随机的填充数组元素*/ 
  17.         int ran_num=rand()% size; 
  18.         array_list[i] = ran_num; 
  19.     } 
  20.     print_list(array_list,size); 
  21.     count_sort(array_list, array_list_a, size); 
  22.     print_list(array_list_a,size); 
  23.     delete array_list; 
  24.     delete array_list_a; 
  25.     return 0; 
  26. /*假设输入的数据都是介于0 - k 的数*/ 
  27. void count_sort(int * array_list_a,int * array_list_b,int k) 
  28.     int * c = new int [sizeof(int) * k]; 
  29.     for(int i=0;i<k;i++) 
  30.     {/*初始化临时数组*/ 
  31.         c[i] = 0; 
  32.     } 
  33.     for(int i=0;i<size;i++) 
  34.     {/*对于输入数组的重复的数值进行统计,在临时数组c的相应的位置予以记录*/ 
  35.         c[array_list_a[i]] += 1;   
  36.     } 
  37.     for(int i=1;i<k;i++) 
  38.     {/*小于当前数据元素的个数*/ 
  39.         c[i] += c[i-1]; 
  40.     } 
  41.     for(int j=size-1;j>=0;j--) 
  42.     { 
  43.         array_list_b[c[array_list_a[j]] - 1] = array_list_a[j]; 
  44.         c[array_list_a[j]] -= 1; 
  45.     } 
  46.     delete c; 
  47. void print_list(int * array_list,int length) 
  48.     for(int i=0;i<length;i++) 
  49.     { 
  50.         std::cout<<array_list[i]<<"\t"
  51.     } 
  52.     std::cout<<std::endl; 

相关推荐