- 首页 > it技术 > >
#include
#include
#include
#include
#define MAXLEN 10typedef struct
{
int key;
int value[MAXLEN];
int len;
}SortType;
void printA(int a[],int len)
{
for(int i=1;
i<=len;
i++)
{
printf("%d ",a[i]);
}
printf("\n");
}void countingSort(int a[],int *b,int len,int k,int n)
{
SortType *c=(SortType*)malloc((k+1)*sizeof(SortType));
int i;
for(i=0;
i<=k;
i++)
{
c[i].key=0;
c[i].len=0;
}
for(i=1;
i<=len;
i++)
{
int k2=a[i]%(int)pow(10.0,n);
k2=k2/(int)pow(10.0,n-1);
c[k2].key++;
c[k2].len++;
c[k2].value[c[k2].len]=a[i];
}
for(i=1;
i<=k;
i++)
{
c[i].key+=c[i-1].key;
}
for(i=len;
i>=1;
i--)
{
int k2=a[i]%(int)pow(10.0,n);
k2=k2/(int)pow(10.0,n-1);
b[c[k2].key]=c[k2].value[c[k2].len];
c[k2].key--;
c[k2].len--;
}
free(c);
}void radixSort(int a[],int len,int n,int N)
{
if(n>N)
return;
int *b=(int*)malloc((len+1)*sizeof(int));
countingSort(a,b,len,9,n);
//printA(b,len);
for(int j=0;
j<=len;
j++)
{
a[j]=b[j];
}
radixSort(a,len,++n,N);
free(b);
}void main()
{
int a[6]={INT_MIN,987,976,654,632,321};
radixSort(a,5,1,3);
printA(a,5);
getchar();
}
推荐阅读
