算法的步骤如下：

（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

最后编辑于：2020.05.12 14:39:07