基数排序原理（java实现）

ゝ一纸荒年。 2022-06-10 10:28 174阅读 0赞

基数排序也是排序算法的一种，老规矩，先来看看百度百科的定义：基数排序（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\}，为什么变成这样了，废话少说，直接上图，字有些丑……嗯……  
　　![这里写图片描述][SouthEast]  
　　相信能看出来规律吧，从前往后，21，放到1号桶中（我们姑且先把他叫做桶），56放到6号桶中，88放到8号桶……放完之后，再把他们按顺序拿出来，就变成了\{21,1,12,354,195,35,56,6,7,88\}，很好理解，对吧，之后再按照这样的方法，把十位，百位，都排一遍，当你排完百位的时候，你就发现，数组变得有序了，由于过程跟上面差不多，博主就直接上图，不再赘述了  
　　  
　　按十位排序  
　　![这里写图片描述][SouthEast 1]  
　　  
　　按百位排序  
　　![这里写图片描述][SouthEast 2]  
　　  
　　好了，当你按照最高位，也就是百位，排序出来了之后，整个数组就变得有序了，这，就是从低位到高位基数排序LSD  
　　  
　　博主刚开始看的时候也是十分不解，真心建议读者，拿张纸，拿根笔，看着下面的代码，自己走一走步骤，从代码的第一行开始走，走完你就会发现这个基数排序的神奇之处了，分享一下博主在理解的时候的草稿纸~  
　　![这里写图片描述][SouthEast 3]  
　　  
　　下面是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;
        }
    }

[SouthEast]: /images/20220610/17e640bdcc4e42439787b891eb90a6ee.png
[SouthEast 1]: /images/20220610/e6625aa2d50f46eab32ec4762cebcef2.png
[SouthEast 2]: /images/20220610/21ea080c853340f1bbeb2ed6d7ba7ef1.png
[SouthEast 3]: /images/20220610/1aa3251998dd456abb5e18ecd5cb46f5.png