8、基数排序

8.1 算法的目标

对数组按照升序/降序进行排序
8.2 算法的思想

将整数按位数切割成不同的数字，然后按每个位数分别比较。
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

8.3 算法的具体步骤

将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序。

step1：找出元素的最大值→→确认排序的次数（例如最大的值为三位数，则进行3次排序，分别对个位、十位、百位进行排序）

step2： 事先准备一个长度为10的二维数组(即代表10个桶)， 分别为0-9号桶， 分别对应个位、十位、百位数的0-9
事先准备一个长度为10的一维数组count[10]，表示0-9编号的桶存放的元素的数量

step3：计算每个元素的个位、十位、百位…… （计算余数）

step4 ：根据余数的值放入对应的二维数组中，并统计对应的桶中的元素数量

step5：第一次排序，对个位数进行排序放入相应的桶中
然后从 0-9 个数组/桶中依次按照加入元素的先后顺序取出
得到{542, 53, 3, 14, 214, 748}

step6：第二次排序，对十位数进行排序放入相应的桶中
然后从 0-9 个数组/桶中依次按照加入元素的先后顺序取出
得到{3，14，214，542，748，53}

step7：第三次排序，对百位数进行排序放入相应的桶中
然后从 0-9 个数组/桶中依次按照加入元素的先后顺序取出
得到{3，14，53，214，542，748}

{
        //找到数组的最大元素，确认排序的次数（排序的次数即为元素的位数）
        int max=nums[0];
        for (int i = 1; i <nums.length ; i++) {
            if (nums[i]>max){
                max=nums[i];
            }
        }
        //确定需要排序的次数
        int len=(max+"").length();
        //定义一个二维数组0-9，来存放对应的位数值
        int temp[][]=new int[10][nums.length];
        //定义一个一维数组，来表示每个桶的存放的个数
        int count[]=new int[10];
        //总共需要排序的次数
        //分别根据元素的个位、十位、百位……进行比较排序
        for (int i = 0,j=1; i < len; i++,j*=10) {
            //计算每个元素的余数，放入指定位置
            for (int k = 0; k < nums.length; k++) {
                int rest=nums[k]/j%10;
                //根据余数存入对应的数组当中
                temp[rest][count[rest]]=nums[k];
                count[rest]++;
            }
            int index=0;
            //按照0-9的顺序依次取出每个桶的元素
            for (int k = 0; k <count.length; k++) {
                if (count[k]!=0){
                    for (int l = 0; l <count[k] ; l++) {
                        nums[index++]=temp[k][l];
                    }
                }
                //取完元素后需要将对应桶的数量置为0
                count[k]=0;
            }
        }
    }