欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基数排序原理(java实现)

程序员文章站 2024-02-06 23:29:46
...

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