計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

（1）算法的步驟：

1. 找出待排序的數(shù)組中最大和最小的元素

2. 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)

3. 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）

4. 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1

（2）計(jì)數(shù)排序的特性總結(jié)：

1. 計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是適用范圍及場(chǎng)景有限。

2. 時(shí)間復(fù)雜度：O(MAX(N,范圍))

3. 空間復(fù)雜度：O(范圍)

4. 穩(wěn)定性：穩(wěn)定 

（3）動(dòng)圖演示：

（4）C語(yǔ)言代碼實(shí)現(xiàn)如下：

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

//交換數(shù)值
void swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
//打印數(shù)組
void printArray(char msg[],int arr[],int len){
    printf("%s:",msg);
    for (int i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}
//計(jì)數(shù)排序(穩(wěn)定)
void count_sort(int a[],int len){
    //計(jì)算出元素最大值和最小值
    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;
    }
    //算出最大臨時(shí)數(shù)組長(zhǎng)度
    int arrlength= maxvalue-minvalue+1;
    //用來存放最終有序數(shù)組
    int *arr=(int*) malloc(arrlength * sizeof(int));
    //用于元素計(jì)數(shù)
    int *temp=(int*) malloc(arrlength * sizeof(int));
    //初始化為0
    for(int k=0;k<arrlength;k++){
        temp[k]=0;
    }
    //temp下標(biāo)即為數(shù)組a[i]相對(duì)mivalue值，每次算出對(duì)應(yīng)的temp下標(biāo)則自增++，遇到相同的元素temp[pos]>1
    for(int i=0;i<len;i++){
        temp[a[i]-minvalue]++;
    }
    printf("元素計(jì)數(shù)：\n");
    for(int i=0;i<arrlength;i++){
        printf("temp[%d]=%d\n",i+minvalue,temp[i]);
    }
    //使用累加(temp[n]=temp[n]+temp[n-1]，有點(diǎn)類似斐波那契數(shù)列)計(jì)算出元素所在位置，保證結(jié)果有序
    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數(shù)組的下標(biāo)
        int pos = a[j]-minvalue;
        //獲取元素位置mappos，--temp[pos]：每放一個(gè)元素到數(shù)組arr，temp[pos]值自減，保證結(jié)果穩(wěn)定有序
        int mappos=(--temp[pos]);
        arr[mappos]=a[j];
    }
    //回填到a數(shù)組
    for(int j=0;j<len;j++){
        a[j]=arr[j];
    }
    //釋放內(nèi)存
    free(arr);
    free(temp);
}
int main()
{
    int len=10;
    int arr[len];
    srand((unsigned)time(NULL));
    //隨機(jī)生成長(zhǎng)度為"len"的數(shù)組
    for(int i=0;i<len;i++){
        arr[i]=rand()%200;
    }
    printArray("未排序前",arr,len);
    count_sort(arr,len);
    printArray("計(jì)數(shù)排序：",arr,len);
    //防止windows下控制臺(tái)窗口閃退
    int s;
    scanf("%d",&s);
    return 0;
}

如果我們編譯并運(yùn)行上述程序，那么它應(yīng)該產(chǎn)生以下結(jié)果：

未排序前:149 192 114 163 65 178 72 154 98 112 
元素計(jì)數(shù)：
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
計(jì)數(shù)排序：:65 72 98 112 114 149 154 163 178 192