计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法的步骤如下：

（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

动图演示

image

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

//交换数值
void swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
//打印数组
void printArray(char msg[],int arr[],int len){
    printf("%s:",msg);
    for (int i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}
//计数排序(稳定)
void count_sort(int a[],int len){
    //计算出元素最大值和最小值
    int maxvalue=a[0],minvalue=a[0];
    for(int x=0;x<len;x++){
        maxvalue=a[x]>maxvalue?a[x]:maxvalue;
        minvalue=a[x]<minvalue?a[x]:minvalue;
    }
    //算出最大临时数组长度
    int arrlength= maxvalue-minvalue+1;
    //用来存放最终有序数组
    int *arr=(int*) malloc(arrlength * sizeof(int));
    //用于元素计数
    int *temp=(int*) malloc(arrlength * sizeof(int));
    //初始化为0
    for(int k=0;k<arrlength;k++){
        temp[k]=0;
    }
    //temp下标即为数组a[i]相对mivalue值，每次算出对应的temp下标则自增++，遇到相同的元素temp[pos]>1
    for(int i=0;i<len;i++){
        temp[a[i]-minvalue]++;
    }
    printf("元素计数：\n");
    for(int i=0;i<arrlength;i++){
        printf("temp[%d]=%d\n",i+minvalue,temp[i]);
    }
    //使用累加(temp[n]=temp[n]+temp[n-1]，有点类似斐波那契数列)计算出元素所在位置，保证结果有序
    for(int j=1;j<arrlength;j++){
            temp[j]+=temp[j-1];
    }
    printf("元素位置：\n");
    for(int i=0;i<arrlength;i++){
        printf("temp[%d]=%d\n",i+minvalue,temp[i]);
    }
    for(int j=len-1;j>=0;j--){
        //获取a[j]在temp数组的下标
        int pos = a[j]-minvalue;
        //获取元素位置mappos，--temp[pos]：每放一个元素到数组arr，temp[pos]值自减，保证结果稳定有序
        int mappos=(--temp[pos]);
        arr[mappos]=a[j];
    }
    //回填到a数组
    for(int j=0;j<len;j++){
        a[j]=arr[j];
    }
    //释放内存
    free(arr);
    free(temp);
}
int main()
{
    int len=10;
    int arr[len];
    srand((unsigned)time(NULL));
    //随机生成长度为"len"的数组
    for(int i=0;i<len;i++){
        arr[i]=rand()%200;
    }
    printArray("未排序前",arr,len);
    count_sort(arr,len);
    printArray("计数排序：",arr,len);
    //防止windows下控制台窗口闪退
    int s;
    scanf("%d",&s);
    return 0;
}

运行结果：

未排序前:2 4 6 2 5 0 5 8 4 9
元素计数：
temp[0]=1
temp[1]=0
temp[2]=2
temp[3]=0
temp[4]=2
temp[5]=2
temp[6]=1
temp[7]=0
temp[8]=1
temp[9]=1
元素位置：
temp[0]=1
temp[1]=1
temp[2]=3
temp[3]=3
temp[4]=5
temp[5]=7
temp[6]=8
temp[7]=8
temp[8]=9
temp[9]=10
计数排序：:0 2 2 4 4 5 5 6 8 9