1、概念

基数排序 也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

2、基本思想

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

3、代码实现

 public  static   void  main(String[] args) {
        //定义整型数组
        int[] a = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        //输出排序前的数组
        for(int i : a)
        {
            System.out.print(i + " ");
        }
        System.out.println();
        //调用基数排序函数
        radixsort(a,5);
        /**
         * 注意这个地方必须要标注数据列中最大数的位数
         * 这里的5表示的是序列里的数字长度最大值为5
         */        
        //输出排序后的数组
        for(int i : a)
        {
            System.out.print(i + " ");
        }
    }

    //a是要排序的数组，d是数组中最大的数的位数
    public static void radixsort(int[] a, int d) 
    {
        //count用来计数
        int[] count = new int[a.length];
        //bucket用来当桶
        int[] bucket = new int[a.length];
        //i表示第几位，1是个位，2是十位，。。。
        for(int i=1;i<=d;i++)
        {
            for(int j=0;j<a.length;j++)
            {
                count[j] = 0;
            }
            //循环统计每个桶中的数据的数量
            for(int j=0;j<a.length;j++)
            {
                count[getFigure(a[j],i)]++;
            }
            //利用count[j]来确定放置数据的位置
            for(int j=1;j<a.length;j++)
            {
                count[j] = count[j] + count[j-1];
            }
            //执行完此循环后的count[j]就是第j个桶右边界的位置
            
            
            //利用循环把数据装入桶中，注意是从后往前
            for(int j=a.length-1;j>=0;j--)
            {
                int k=getFigure(a[j],i);
                bucket[count[k] - 1] = a[j];
                count[k]--;
            }
            //将桶中的数据取出，赋值给a
            for(int j=0,k=0;j<a.length;j++,k++)
            {
                a[j] = bucket[k];
            }
        }
    }
    //此函数返回整型数j的第i位是什么
    public static int getFigure(int j,int i)
    {
        int[] a = {1,10,100,1000,10000,100000};
        return (j/a[i-1])%10;
    }