算法导论计数排序实现

算法导论计数排序实现

空间换时间，时间复杂度是线性的。

#include <stdio.h>
#include <stdlib.h>

void countsort(int a[],int b[],int c[],int k,int length)
{

int i=0,j=0;
for(j=0;j<length;++j)
    {
        c[a[j]]=c[a[j]]+1;
    }
for(i=1;i<k;++i)
    {
        c[i]=c[i]+c[i-1];
    }
for(j=length-1;j>0;j--)
    {
        b[c[a[j]]]=a[j];
        c[a[j]]=c[a[j]]-1;
    }
}

int main()
{
int a[]={2,5,3,0,2,3,0,3};
int b[8]={0};
int c[6]={0};

    countsort(a,b,c,6,sizeof(a)/sizeof(int));
int i=0;
for(i=0;i<sizeof(a)/sizeof(int);++i)
printf("%d ",b[i]);
return 0;
}