计数排序的基本思想为:对每一个输入的元素x,确定出小于x的元素的个数。有了这一信息,那么就可以把x直接放到相应的位置上。
特点:
1 需要临时的存储空间,如果排序数据范围特别大时,空间开销很大。
2 适合于排序0 - 100以内的数据。
3 排序的时间复杂度为O(n)。
#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; }