[算法导论]c++实现计数排序

计数排序的基本思想为：对每一个输入的元素x，确定出小于x的元素的个数。有了这一信息，那么就可以把x直接放到相应的位置上。
特点：
1 需要临时的存储空间，如果排序数据范围特别大时，空间开销很大。
2 适合于排序0 - 100以内的数据。
3 排序的时间复杂度为O(n)。
[cpp] 
#include <iostream> 
#include <string> 
 
const int size = 100; 
int * array_list; 
int * array_list_a; 
void print_list(int * ,int ); 
void count_sort(int * ,int * ,int ); 
 
int main(int argc,char * argv[]) 
{ 
     
    array_list = new int [sizeof(int)*size]; 
    array_list_a = new int [sizeof(int)*size]; 
    srand(0); 
    for(int i=0;i<size;i++) 
    {/*随机的填充数组元素*/ 
        int ran_num=rand()% size; 
        array_list[i] = ran_num; 
    } 
    print_list(array_list,size); 
    count_sort(array_list, array_list_a, size); 
    print_list(array_list_a,size); 
    delete array_list; 
    delete array_list_a; 
    return 0; 
} 
/*假设输入的数据都是介于0 - k 的数*/ 
void count_sort(int * array_list_a,int * array_list_b,int k) 
{ 
    int * c = new int [sizeof(int) * k]; 
    for(int i=0;i<k;i++) 
    {/*初始化临时数组*/ 
        c[i] = 0; 
    } 
    for(int i=0;i<size;i++) 
    {/*对于输入数组的重复的数值进行统计，在临时数组c的相应的位置予以记录*/ 
        c[array_list_a[i]] += 1;  
    } 
    for(int i=1;i<k;i++) 
    {/*小于当前数据元素的个数*/ 
        c[i] += c[i-1]; 
    } 
    for(int j=size-1;j>=0;j--) 
    { 
        array_list_b[c[array_list_a[j]] - 1] = array_list_a[j]; 
        c[array_list_a[j]] -= 1; 
    } 
    delete c; 
} 
void print_list(int * array_list,int length) 
{ 
    for(int i=0;i<length;i++) 
    { 
        std::cout<<array_list[i]<<"\t"; 
    } 
    std::cout<<std::endl; 
} 
作者：Harry_lyc

补充：软件开发 , C++ ,