在之前的文章中给大家介绍过一种非比较排序——计数排序，计数排序呢是通过一个数组来统计每次数字出现的次数，然后按照大小顺序依次放回原数组，结束排序。但是计数排序只针对于整型，无法对字符串进行排序，所以，为了改进这一缺陷，出现了一个他的“升级版”排序——基数排序。
他两名字也比较相近，基数排序也是非比较排序，排序中逻辑相比较而言简单的一种排序，属于分配排序类型，也称之为“桶子法”。
基数排序在计数排序上进行一些改进，将排序的过程分为多阶段，每一个阶段呢都会把一个字符串分成一个一个字符来进行排序，数字也是一样的，多位数分成一个数一个数单独进行排序。
假如现有待排序数组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(" ");
return 0;
}
3279916262