基数排序算法回顾---（韩顺平数据结构）笔记

属于“分配式排序”又称“桶子法”该算法是通过键值的各个位的值，将要排序的元素分配至“桶”中，达到排序的作用

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

将整数位切割成不同的数字，然后按每个位数进行比较

将所有的比较数值统一为同样的数位长度，数位较短的数前面补零，然后，从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位排序完成后，数列就变成一个有序序列。

时间复杂度：
每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。系数2可以省略，且无论数组是否有序，都需要从个位排到最大位数，所以时间复杂度始终为O(d * n) 。其中，n是数组长度，d是最大位数。

空间复杂度：
基数排序的空间复杂度为O(n+k)，其中k为桶的数量，需要分配n个数。

将数组{53, 3, 542, 748, 14, 214}进行排序（使用升序）
根据计算求出最大值为3位数，所以需要三轮排序

第一轮
第二轮
第三轮

package sort;

import java.util.Arrays;

public class RadixDemo {

    public static void main(String[] args) {
        int arr[] = {53, 3, 542, 748, 14, 214};
        radix(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radix(int [] arr){

        int max = arr[0];

        // for 求出最大值
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]){
                max = arr[i];
            }
        }

//        定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
        int[][] bucket = new int[10][arr.length];
        
        //为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //可以这里理解
        //比如：bucketElementCounts[0] , 记录的就是  bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];

        //得到最大数是几位数
        int maxLength = (max + "").length();

        // 一共遍历 maxLength次 第一次是个位，第二次是十位，第三次是百位...
        for (int i = 0,n = 1; i < maxLength; i++,n *= 10) {
            
            //(针对每个元素的对应位进行排序处理)， 
            // 遍历完毕所有的数 arr.length
            for (int j = 0; j < arr.length; j++) {
                // 求出每次遍历（个，十，百....）位数的值
                int in = arr[j] / n %10 ;
                // 将该数字 填充到 （in ， bucketElementCounts[in]）这个位置
                bucket[in][bucketElementCounts[in]] = arr[j];
                
                // 方便记录 符合 位数为某个值的数字集合
                bucketElementCounts[in]++;
            }

            //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
            int index = 0;
            //遍历每一桶，并将桶中的数据，放入到原数组
            for (int  k = 0 ;k < bucketElementCounts.length;k++){
                //如果桶中，有数据，我们才放入到原数组
                if(bucketElementCounts[k] != 0){
                    //循环该桶即第k个桶(即第k个一维数组), 放入
                    for (int j = 0; j < bucketElementCounts[k]; j++) {
                        arr[index++] = bucket[k][j];
                    }
                }
                //第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
                bucketElementCounts[k] = 0;
            }
        }


    }

}