在之前的文章中给大家介绍过一种非比较排序——计数排序，计数排序呢是通过一个数组来统计每次数字出现的次数，然后按照大小顺序依次放回原数组，结束排序。但是计数排序只针对于整型，无法对字符串进行排序，所以，为了改进这一缺陷，出现了一个他的“升级版”排序——基数排序。

他两名字也比较相近，基数排序也是非比较排序，排序中逻辑相比较而言简单的一种排序，属于分配排序类型，也称之为“桶子法”。

基数排序在计数排序上进行一些改进，将排序的过程分为多阶段，每一个阶段呢都会把一个字符串分成一个一个字符来进行排序，数字也是一样的，多位数分成一个数一个数单独进行排序。

假如现有待排序数组A[]={2,8,13,23,5,21,18,12,19}; 有0-9的范围的9个桶（如图1-1所示）

图1-1

现在把数组中每个数统一成相同的数位长度，数位较短的在前面补零。现在把每个数分成单独的数字，每个数从个位数进行排序，放入相应的桶里面（如图1-2所示）   

图1-2      

经过第一轮的排序，目前数组内的元素顺序为21、2、12、13、23、5、8、18、19。  

继续开始第二轮的排序，把十位数的数字单独分出来，依次放入对应的桶里面（如图1-3所示）

图1-3

第二轮排序结束之后，再把元素依次放回数组里A[]={2,5,8,12,13,18,19,21,23}；基数排序结束。

 

详细代码：

#include<stdio.h>

#include<string.h>

#define N 10 //数组长度

#define D 10 //最大位数

 

int GetDigit(int M, int i) //取整数M的第i位数

{

while(i > 1)

{

M /= 10;

i--;

}

return M % 10;

}

 

void RadixSort(int num[], int len)

{

int i, j, k, l, digit;

int allot[10][N]; //分配数组

 

memset(allot, 0, sizeof(allot));//初始化分配数组

 

for(i = 1; i <= D; i++)

{

//分配相应位数的数据，并存入分配数组

for(j = 0; j < len; j++)

{

digit = GetDigit(num[j], i);

k = 0;

while(allot[digit][k])

k++;

allot[digit][k] = num[j];

}

//将分配数组的数据依次收集到原数组中

l = 0; 

for(j = 0; j < 10; j++)

{

k = 0;

while(allot[j][k] > 0)

{

num[l++] = allot[j][k];

k++;

}

}

//每次分配，收集后初始化分配数组，用于下一位数的分配和收集

memset(allot, 0, sizeof(allot));

}

}

 

int main()

{

int num[N] = {52, 20, 4, 10, 17, 39, 8, 300, 60, 81};

 

RadixSort(num, N);

 

for(int i = 0; i < N; i++)

printf("%d ", num[i]);

printf("\n");

return 0;

}