计数排序

计数排序C语言版：

​#include<stdio.h>
#include<malloc.h>
void CountingSort(int a[],int a_length,int k);
int main(){
    int k=10;
    int a[]={0,9,5,6,8,7,9,0,2,0,6,3,7,1,4,6,3,10};
    int a_length=sizeof(a)/sizeof(int);
    CountingSort(a,a_length,k);
    //b是输出数组，先初始化
     printf("计数排序后为：\n");
    for(int i=0;i<a_length;i++){
        printf("%d ",a[i]);
    }
}
void CountingSort(int a[],int a_length,int k){
    int *b=(int*)malloc(a_length*sizeof(int));//数组a排好序保存在b中
    for(int i=0;i<a_length;i++){ //对b数组初始化
        b[i]=0;
    }
    int *c=(int*)malloc((k+1)*sizeof(int));//c为计数数组
    for(int i=0;i<k+1;i++){            //c数组初始化
        c[i]=0;
    }
    for(int i=0;i<a_length;i++){  //0~k的每个数在数组a中出现的次数保存在c中
        c[a[i]]+=1;
    }
    for(int i=1;i<=k;i++){     //对c中小于等于c[i]的数进行累加并保存在c[i]中
        c[i]+=c[i-1];
    }
    for(int i=a_length-1;i>=0;i--){  //从a中的最后一个数开始，通过数据出现的次数与小标的关系可以确定应放在数组的哪个位置
        b[c[a[i]]-1]=a[i];
        c[a[i]]-=1;
    }
    for(int i=0;i<a_length;i++){    //b复制到a中
        a[i]=b[i];
    }
}
​