计数排序 --Counting

前提条件

数据的范围必须是有确定范围的整数。
一般用于取值范围比较小，数据量比较大。

image

设计思想

//50 -- 150
#define BASE 50
#define MAX_NUM 100

1. 申请两个数组
   1)结果数组，和原数组等长
   2)Count数组，长度和取值范围等长。

    int* arraysort = calloc(arraysize,sizeof(int)  );
    int* arraycount = calloc(MAX_NUM,sizeof(int)  );
    int index;
     for(int i=0;i<MAX_NUM;i++)
        arraycount[i] = 0;

2. 记录每个数，出现的次数

    //count
    for(int i=0;i<arraysize;i++){
        index = array[i];
        if((index<BASE)||(index>BASE+MAX_NUM-1))
        {
            printf("wrong source out of range \n");
            continue;
        }
        arraycount[index-BASE]++;
    }

3. 对所有的计数累加，是为了能够知道每个最后数出现位置。
   为了稳定的目的。

    for(int i=1;i<MAX_NUM;i++){
        arraycount[i] = arraycount[i] + arraycount[i-1];

4. 从最后一个开始填充结果数组。

    for(int i=arraysize-1;i>=0;i--){
        arraycount[array[i]-BASE]--;
        arraysort[arraycount[array[i]-BASE]] = array[i];
    }

复杂度

时间复杂度是O(n+k)，空间复杂度也是O(n+k)