基数排序算法思路图解

基数排序(桶排序)介绍:

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用

基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法

基数排序(Radix Sort)是桶排序的扩展

基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序轮数取决于原数组中最大数的位数

基数排序代码实现

用二维数组表示10个桶，为了防止放入数据时溢出，每个一位数组的大小都定义为arr.length,基数排序是用空间换时间

取每个桶中的数据时不确定每个桶中有几个元素？
每放入一次数据就要记录每一个桶中有几个有效数据（定义一个一位数组来记录放入数据的个数）
int[] bucketElementCounts
第一轮 排序，按个位数存进桶

public static void baseSort(int arr[])
    {
       //创建一个二维数组，每一维存放个位相同的数 比如第0维就存放个位为0的数
        int[][]Digit=new int[10][arr.length];
        //定义一个一维数组，计数每一维是否存有数据
        int[]DimCount=new int[10];
        //第一轮排序，按个位存进十个桶
        System.out.println("第一轮排序，按个位存进十个桶");
        for(int i=0;i<arr.length;i++)
        {
            Digit[arr[i]%10][DimCount[arr[i]%10]]=arr[i];//找出待排序数的个位数，然后存进和这个个位数相应的桶，个位是1，就存进编号为1的桶（即Digit[0][]），个位是10，就存进编号为0的桶（即Digit[1][]）
            DimCount[arr[i]%10]++;//哪个桶存进了数，这个桶中的数的数量就加1，方便后续再存入数，DimCount[arr[i]%10]是二维数组Digit的第二个下标
        }
        for(int i=0;i<10;i++)
        {
            for(int j=0;j<arr.length;j++)
            {
                System.out.print(Digit[i][j]+" ");
            }
            System.out.println();//打印一行就换行
        }
    }

测试 int[]arr={123,36,78,58,94,63,72,45};

第一轮排序，按个位存进十个桶
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
72 0 0 0 0 0 0 0 
123 63 0 0 0 0 0 0 
94 0 0 0 0 0 0 0 
45 0 0 0 0 0 0 0 
36 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
78 58 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 

第二轮 排序，按十位数存进桶
每一轮排完记得清桶里面的数据，把负责基数的数组清空即可，这样我们下一次王桶里放数据就是从每个桶的下标0开始存，在把这个下标对应的桶中的元素数量加1，我们排完从桶种取出数据的时候，只取到每一个桶对应的计数就好了。

   //把第一轮拍好序的数从桶里拿出来放进数组，第二轮再对这个数组进行排序
        int count=0;
         for(int i=0;i<10;i++)
         {
             for(int j=0;j<DimCount[i];j++)
             {
                 arr[count++]=Digit[i][j];
             }
             DimCount[i]=0;//把计数清零，以便下一轮排序再往二维数组放数据
         }

 //第二轮排序，按十位存进十个桶
        System.out.println("第二轮排序，按十位存进十个桶");

        for(int i=0;i<arr.length;i++)
        {
            Digit[arr[i]/10%10][DimCount[arr[i]/10%10]]=arr[i];//找出待排序数的十位数，然后存进和这个十位数相应的桶，十位是1，就存进编号为1的桶（即Digit[1][]）
            DimCount[arr[i]/10%10]++;
        }

第三轮 排序，按百位数存进桶
每一轮排完记得清桶里面的数据

        //第三轮排序，按百位存进十个桶
        System.out.println("第三轮排序，按百位存进十个桶");

        for(int i=0;i<arr.length;i++)
        {
            Digit[arr[i]/100%10][DimCount[arr[i]/100%10]]=arr[i];//找出待排序数的十位数，然后存进和这个十位数相应的桶，十位是1，就存进编号为1的桶（即Digit[1][]）
            DimCount[arr[i]/100%10]++;
        }

        count=0;
        for(int i=0;i<10;i++)
        {
            for(int j=0;j<DimCount[i];j++)
            {
                arr[count++]=Digit[i][j];
            }
            DimCount[i]=0;//把计数清零，以便下一轮排序再往二维数组放数据
        }
        System.out.println(Arrays.toString(arr));

接下来我们把代码合并

public static void BaseSort2(int arr[]) {

        //创建一个二维数组，每一维存放个位相同的数 比如第0维就存放个位为0的数
        int[][] Digit = new int[10][arr.length];
        //定义一个一维数组，计数每一维是否存有数据
        int[] DimCount = new int[10];

        //先获取外循环的轮数，最多3位数就循环3轮，所以需要先找到最大的数是几位的
        int  max=0;
        for(int i=0;i<arr.length;i++)
        {
            if(arr[i]>max)
            {
                max=arr[i];
            }
        }
        int maxLength=(max+"").length();//骚操作，转成字符串看长度

        for (int k = 0,n=1; k < maxLength; k++,n*=10) {//注意n*=10，自己理解一下吧，结合分部循环
            for (int i = 0; i < arr.length; i++ ) {
                Digit[arr[i] / n % 10][DimCount[arr[i] / n % 10]] = arr[i];//找出待排序数的个位数，然后存进和这个个位数相应的桶，个位是1，就存进编号为1的桶（即Digit[1][]），个位是0，就存进编号为0的桶（即Digit[0][]）
                DimCount[arr[i] / n % 10]++;//哪个桶存进了数，这个桶中的数的数量就加1，方便后续再存入数，DimCount[arr[i]%10]是二维数组Digit的第二个下标
            }
            //把上一轮排好序的数从桶里拿出来放进数组，下一轮再对这个数组进行排序
            for (int i = 0, count = 0; i < 10; i++) {
                for (int j = 0; j < DimCount[i]; j++) {
                    arr[count++] = Digit[i][j];
                }
                DimCount[i] = 0;//把计数清零，以便下一轮排序再往二维数组放数据
            }
            System.out.println(Arrays.toString(arr));
        }
    }

我们再来测试80个数据
好测试无误，我们测试一下80000个数需要排序多久

800000

8000000

80000000

基数排序算法注意事项

当数据量较小，速度比快排和归并还快，但是当数据量比如达到8000万，因为排序之前会开10个桶，每个桶的长度都跟数据量一样大，那么占用内存（空间）就会很大

80000000×11×4/1024/1024/1024=3.3G，占用内存3.3个G（相当于11个数组，一个int是4个字节，1k=1024字节，1M=1024k,1G=1024M）
基数排序的稳定性说明
3 1 4 1 5 7 2
排序之后
1 1 2 3 4 5 7
可以看到数组里面有2个 1，排序前后，两个1的顺序是不变的，原来哪一个1在前面，排序之后它依然在前面

基数排序的说明:
基数排序是对传统桶排序的扩展，速度很快.
基数排序是经典的空间换时间的方式，占用内存很大,（因为我们开了一个二维数组） 当对海量数据排序时，容易造成 OutOfMemoryError 。
基数排序是稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]
有负数的数组，我们不用基数排序来进行排序, 如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9

负数排序方案：取余的绝对值放入桶中，再取出来数据时要进行反转