/*rxsort.c*/
#include <limits.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
/***************************************************************
*用基数排序对十进制数进行排序
*参数: data:数组元素 size:数组中元素的个数
* p:元素中最大的位数; k :基数 (十,八,二,16,进制等等)
*返回值 :成功0,失败-1;
* 函数有运行结束后,已排序好的序列保存在data中
**************************************************************/
int rxsort(int *data, int size, int p, int k)
{
int * counts,/*计数数组*/
* temp;/*临时保存排序后的数组*/
int index,
pval,
i,
j,
n;
/*申请空间*/
if ((counts = (int *)malloc(k * sizeof(int))) == NULL)
return -1;
if ((temp = (int *)malloc(size * sizeof(int))) == NULL)
return -1;
/*从低位到高位分别进行排序*/
for (n = 0; n < p; n++){
/*计数数组初始化*/
for ( i = 0; i < k; i ++)
counts[i] = 0;
/*计算当前位的基数*/
pval = (int) pow((double )k, (double)n);
/*下面的实现参数计数排序部分*/
for (j = 0; j < size; j ++){
index = (data[j]/pval)%pval;
counts[index] += 1;
}
for (i = 1; i < k; i ++)
counts[i] += counts[i - 1];
for(j = size - 1; j >= 0; j --){
index = (data[j]/pval)%pval;
temp[counts[index] - 1] = data[j];
counts[index] -= 1;
}
memcpy(data, temp, size *sizeof(int));
}
free(counts);
free(temp);
return 0;
}
int main()
{
int a[20] = {20,300,40,5,80,12,500,43,23,56,121,33,444,555,666,112,456,234,123,124};
int i = 0;
rxsort(a,20,3,10);
for (i = 0; i< 20; i++)
printf ("a[%d] = %d\n",i,a[i]);
}