计数排序算法C/C++代码图文讲解

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

（1）算法的步骤：

1. 找出待排序的数组中最大和最小的元素

2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项

3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）

4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

（2）计数排序的特性总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。

2. 时间复杂度：O(MAX(N,范围))

3. 空间复杂度：O(范围)

4. 稳定性：稳定 

（3）动图演示：

（4）C语言代码实现如下：

#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;
}

如果我们编译并运行上述程序，那么它应该产生以下结果：

未排序前:149 192 114 163 65 178 72 154 98 112 
元素计数：
temp[65]=1
temp[66]=0
temp[67]=0
temp[68]=0
temp[69]=0
temp[70]=0
temp[71]=0
temp[72]=1
temp[73]=0
temp[74]=0
temp[75]=0
temp[76]=0
temp[77]=0
temp[78]=0
temp[79]=0
temp[80]=0
temp[81]=0
temp[82]=0
temp[83]=0
temp[84]=0
temp[85]=0
temp[86]=0
temp[87]=0
temp[88]=0
temp[89]=0
temp[90]=0
temp[91]=0
temp[92]=0
temp[93]=0
temp[94]=0
temp[95]=0
temp[96]=0
temp[97]=0
temp[98]=1
temp[99]=0
temp[100]=0
temp[101]=0
temp[102]=0
temp[103]=0
temp[104]=0
temp[105]=0
temp[106]=0
temp[107]=0
temp[108]=0
temp[109]=0
temp[110]=0
temp[111]=0
temp[112]=1
temp[113]=0
temp[114]=1
temp[115]=0
temp[116]=0
temp[117]=0
temp[118]=0
temp[119]=0
temp[120]=0
temp[121]=0
temp[122]=0
temp[123]=0
temp[124]=0
temp[125]=0
temp[126]=0
temp[127]=0
temp[128]=0
temp[129]=0
temp[130]=0
temp[131]=0
temp[132]=0
temp[133]=0
temp[134]=0
temp[135]=0
temp[136]=0
temp[137]=0
temp[138]=0
temp[139]=0
temp[140]=0
temp[141]=0
temp[142]=0
temp[143]=0
temp[144]=0
temp[145]=0
temp[146]=0
temp[147]=0
temp[148]=0
temp[149]=1
temp[150]=0
temp[151]=0
temp[152]=0
temp[153]=0
temp[154]=1
temp[155]=0
temp[156]=0
temp[157]=0
temp[158]=0
temp[159]=0
temp[160]=0
temp[161]=0
temp[162]=0
temp[163]=1
temp[164]=0
temp[165]=0
temp[166]=0
temp[167]=0
temp[168]=0
temp[169]=0
temp[170]=0
temp[171]=0
temp[172]=0
temp[173]=0
temp[174]=0
temp[175]=0
temp[176]=0
temp[177]=0
temp[178]=1
temp[179]=0
temp[180]=0
temp[181]=0
temp[182]=0
temp[183]=0
temp[184]=0
temp[185]=0
temp[186]=0
temp[187]=0
temp[188]=0
temp[189]=0
temp[190]=0
temp[191]=0
temp[192]=1
元素位置：
temp[65]=1
temp[66]=1
temp[67]=1
temp[68]=1
temp[69]=1
temp[70]=1
temp[71]=1
temp[72]=2
temp[73]=2
temp[74]=2
temp[75]=2
temp[76]=2
temp[77]=2
temp[78]=2
temp[79]=2
temp[80]=2
temp[81]=2
temp[82]=2
temp[83]=2
temp[84]=2
temp[85]=2
temp[86]=2
temp[87]=2
temp[88]=2
temp[89]=2
temp[90]=2
temp[91]=2
temp[92]=2
temp[93]=2
temp[94]=2
temp[95]=2
temp[96]=2
temp[97]=2
temp[98]=3
temp[99]=3
temp[100]=3
temp[101]=3
temp[102]=3
temp[103]=3
temp[104]=3
temp[105]=3
temp[106]=3
temp[107]=3
temp[108]=3
temp[109]=3
temp[110]=3
temp[111]=3
temp[112]=4
temp[113]=4
temp[114]=5
temp[115]=5
temp[116]=5
temp[117]=5
temp[118]=5
temp[119]=5
temp[120]=5
temp[121]=5
temp[122]=5
temp[123]=5
temp[124]=5
temp[125]=5
temp[126]=5
temp[127]=5
temp[128]=5
temp[129]=5
temp[130]=5
temp[131]=5
temp[132]=5
temp[133]=5
temp[134]=5
temp[135]=5
temp[136]=5
temp[137]=5
temp[138]=5
temp[139]=5
temp[140]=5
temp[141]=5
temp[142]=5
temp[143]=5
temp[144]=5
temp[145]=5
temp[146]=5
temp[147]=5
temp[148]=5
temp[149]=6
temp[150]=6
temp[151]=6
temp[152]=6
temp[153]=6
temp[154]=7
temp[155]=7
temp[156]=7
temp[157]=7
temp[158]=7
temp[159]=7
temp[160]=7
temp[161]=7
temp[162]=7
temp[163]=8
temp[164]=8
temp[165]=8
temp[166]=8
temp[167]=8
temp[168]=8
temp[169]=8
temp[170]=8
temp[171]=8
temp[172]=8
temp[173]=8
temp[174]=8
temp[175]=8
temp[176]=8
temp[177]=8
temp[178]=9
temp[179]=9
temp[180]=9
temp[181]=9
temp[182]=9
temp[183]=9
temp[184]=9
temp[185]=9
temp[186]=9
temp[187]=9
temp[188]=9
temp[189]=9
temp[190]=9
temp[191]=9
temp[192]=10
计数排序：:65 72 98 112 114 149 154 163 178 192