根据维基百科，基数排序的定义为： 基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
基数排序的思路是将所有待比较数值（正整数）统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序，这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.
举个栗子：
待排序数列为:324,63,59,225,13
第一次排序（按个位大小排序）：063，013，324，225，059
第二次排序（按十位大小排序）：013，324，225，059，063
第三次排序（按百位大小排序）：013，059，063，225，324
最终输出：13，59，63，225，324
从这个例子可以看出：下一次的排序不会影响上一次排序的结果，即当按照十位排序时如果十位上的数字相同，则它们的排序依然是上一次排序的结果（上述例子中的324与225），所以我们需要稳定排序。什么是稳定排序？
稳定排序的意思是指, 待排序相同元素之间的相对前后关系,在各次排序中不会改变.比如实例中具有十位数字2的两个数字324和225, 在十位排序之前324在225之前,在十位排序之后, 324依然在225之前。稳定排序能保证,上一次的排序成果被保留,十位数的排序过程能保留个位数的排序成果,百位数的排序过程能保留十位数的排序成果.
代码实现上述过程时我们用数组来存放数据和排序结果：
第一次排序（个位数）
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
63 | 324 | 225 | 59 | ||||||
13 | |||||||||
第二次排序（十位数）
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
13 | 324 | 59 | 63 | ||||||
225 | |||||||||
第三次排序（百位数）
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
013 | 225 | 324 | |||||||
059 | |||||||||
063 |
最终将二维数组中的元素按列读出来就是所得结果：
13，59，63，225，324
代码实现：
package acm;/*基数排序*/class RadxSort { public void RSort(int[] ary){ int length = ary.length; int[][] bucket = new int[length][10];//桶用来存放按位排序的数 int[] order = new int[10]; //记录一个桶中有多少个元素 int time = 1;//记录排序次数，即最大数的位数 int n = 1; int k = 0; while(time<=maxDigit(ary)){ for(int i:ary){ int digit = (i/n)%10; //从个位依次往上每位上的数 bucket[order[digit]][digit] = i; order[digit]++;//把桶中的个数加一 } for(int i=0;i<10;i++){ if(order[i]!=0){ for(int j=0;j 算法复杂度分析
基数排序的时间复杂度是O(kn)，其中n是排序元素的个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(nlog(n))，k的大小取决于数字位的选择（比如比特位数），和待排序数据所属数据类型的全集大小；k决定了进行多少轮处理，而n是每轮处理的操作数目。
以排序n个不同的整数来举例，假设这些整数以B为底，这样每位数都有B个不同的数字，K=logBN，N是待排序数据类型的全集的势。虽然有B个不同的数字，需要B个不同的桶，但在每一轮的处理中，判断每个待排序数据项只需要一次计算确定对应数位的值，因此在每一轮处理的时候都需要平均n次操作来把整数放到合适的桶中去，所以有：
K≈logBN
所以，基数排序的平均时间T为：
T≈logB（N）n
其中前一项是一个与输入数据无关的常数，当然该项不一定小于logn
如果考虑和比较排序进行对照，基数排序的形式复杂度虽然不一定更小，但由于不进行比较，因此其基本操作的代价较小，而且在适当选择的B之下，k一般不大于logn，所以基数排序一般要快过基于比较的排序，比如快速排序。