今天看到这种排序方式，觉得很有趣，以前居然没发现还有这种排序方式。从理论上，这种排序方式也是最优（比冒泡，快速这些传统的）的。
基数排序的原理：假设在数组 a=[2,15,7,85,6,94,621,57,62,21,542]中 ，最大的数是一个3位数”621”，那么，其他所有数字都认为是3位数（高位补0），那么，就对这些三位数从个位起排序。第一次，只看所有数的个位数（这里假设从小到大排，个位相同的就按遍历的顺序放就好了），那么就是： “621，021，002，062，542，094，015，085，006，007，057” 然后对上面经过一次排序的数组看十位，结果为： “002，006，007，015，621，021，542，057，062，085，094” 然后百位： “002，006，007，015，021，057，062，085，094，542，621” 也就排好了。
贴一下代码（只考虑正整数）
public class RadixSort { private int search_max(int [] a){//选取数组中最大的数 int max=a[0]; for(int i=1;i<a.length;i++){ if(max<a[i]) max=a[i]; } return max;//返回该最大的数 } private int calculate_radix(int max){//判断这个最大的数为几位数 int radix=1;//最小也是1位数，所以从1开始 while(max%10!=max){ radix++; max /= 10; } return radix;//返回这个几位数 } public int[] radix_sort (int [] a){ int [] temp=new int[a.length];//定义一个与数组a同样大的数组进行排序辅助 int radix=calculate_radix(search_max(a));//数组a的最大位数 for(int k=0;k<radix;k++){//最大位数为多少，也就是需要排序多少次 int value=(int)Math.pow(10, k);//用于确定各个位上的数的除数，例如个位就是除以1。 int index=0;//用于记录当前排列数据已经排到数组的第几位 for(int i=0;i<10;i++){//十进制的基数就是0到9 for(int j=0;j<a.length;j++){ if(k%2==0){//当k为偶数时，以a数组为基础，将排好的数据放到temp数组中 if(a[j]/value%10==i ){ temp[index]=a[j]; index++; } } else{//所以当k为奇数时，应该以temp数组为基础。 if(temp[j]/value%10==i){ a[index]=temp[j]; index++; } } } if(index==a.length)//如果此时index已经等于数组程度，说明所有数据已经都排完了 break; } } //最大位数决定循环的次数，也会决定最后排好的结果在哪个数组里 if(radix%2==0) return a; else return temp; } }main函数
public class mainTest { public static void main(String [] args){ int [] a={2,15,7,85,6,94,621,57,62,21,542}; RadixSort s1=new RadixSort(); a=s1.radix_sort(a); for(int i=0;i<a.length;i++) System.out.print(a[i]+" "); } }以上代码采用顺序循环队列，也可以采用链式队列，两种方法比较，我个人认为，顺序循环队列时间复杂度高一点，大约是多循环10次整个数组，链式队列则空间复杂度高一点，因为他需要创建10（十进制，M进制也就是M个）个队列来存储数据，而顺序循环队列只需要创建一个数组。
代码完全手写，只测试了逻辑是否合理，没有去推敲细节。有问题或者改进的地方，请指教。
