基数排序原理（java实现）

　　基数排序也是排序算法的一种，老规矩，先来看看百度百科的定义：基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
　　
　　基数排序有从低位到高位的排序LSD，也有按照先高位后低位的排序MSD，这里介绍LSD
　　
　　然后，听我的，咱们直接举例子，假定现在有这样一个整型数组{21,56,88,195,354,1,35,12,6,7}，我们可以看到，最大的数，354，是三位数，也就是说，这个排序最大涉及的数就是一个三位数，那么我们该怎么对这个数组运用基数排序呢？听我慢慢说
　　
　　首先，看这些数的个位，把他们按照个位从小到大排序（注意是按照个位），具体怎么排咱们一会儿看代码，先说原理， 也就是说，原来的数组按照个位排序就变成了{21,1,12,354,195,35,56,6,7,88}，为什么变成这样了，废话少说，直接上图，字有些丑……嗯……
　　
　　相信能看出来规律吧，从前往后，21，放到1号桶中（我们姑且先把他叫做桶），56放到6号桶中，88放到8号桶……放完之后，再把他们按顺序拿出来，就变成了{21,1,12,354,195,35,56,6,7,88}，很好理解，对吧，之后再按照这样的方法，把十位，百位，都排一遍，当你排完百位的时候，你就发现，数组变得有序了，由于过程跟上面差不多，博主就直接上图，不再赘述了
　　
　　按十位排序
　　
　　
　　按百位排序
　　
　　
　　好了，当你按照最高位，也就是百位，排序出来了之后，整个数组就变得有序了，这，就是从低位到高位基数排序LSD
　　
　　博主刚开始看的时候也是十分不解，真心建议读者，拿张纸，拿根笔，看着下面的代码，自己走一走步骤，从代码的第一行开始走，走完你就会发现这个基数排序的神奇之处了，分享一下博主在理解的时候的草稿纸~
　　
　　
　　下面是Java代码实现：
　　

class Demo
{
    public static void main(String[] args)
    {
        //定义整型数组
        int[] arr = {21,56,88,195,354,1,35,12,6,7};

        //调用基数排序函数
        lsd_RadixSort(arr,3);

        //输出排序后的数组
        for(int i=0;i<arr.length;i++)
        {
            System.out.print(arr[i]+"  ");
        }
    }

    //arr是要排序的数组，max是数组中最大的数有几位
    public static void lsd_RadixSort(int[] arr,int max)
    {
        //count数组用来计数
        int[] count = new int[arr.length];
        //bucket用来当桶（在下面你就理解了什么是桶了），放数据，取数据
        int[] bucket = new int[arr.length];

        //k表示第几位，1代表个位，2代表十位，3代表百位
        for(int k=1;k<=max;k++)
        {
            //把count置空，防止上次循环的数据影响
            for(int i=0;i<arr.length;i++)
            {
                count[i] = 0;
            }

            //分别统计第k位是0,1,2,3,4,5,6,7,8,9的数量
            //以下便称为桶
            //即此循环用来统计每个桶中的数据的数量
            for(int i=0;i<arr.length;i++)
            {
                count[getFigure(arr[i],k)]++;
            }

            //利用count[i]来确定放置数据的位置
            for(int i=1;i<arr.length;i++)
            {
                count[i] = count[i] + count[i-1];
            }
            //执行完此循环之后的count[i]就是第i个桶右边界的位置

            //利用循环把数据装入各个桶中，注意是从后往前装
            //这里是重点，一定要仔细理解
            for(int i=arr.length-1;i>=0;i--)
            {
                int j = getFigure(arr[i],k);
                bucket[count[j]-1] = arr[i];
                count[j]--;
            }

            //将桶中的数据取出来，赋值给arr
            for(int i=0,j=0;i<arr.length;i++,j++)
            {
                arr[i] = bucket[j];
            }

        }       
    }

    //此函数返回整型数i的第k位是什么
    public static int getFigure(int i,int k)
    {
        int[] a = {1,10,100};
        return (i/a[k-1])%10;
    }
}