基数排序

百度：

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

理解：

把一个待排序的数组按照从个位、十位......进行分类，再按每次分类从0-9(个位、十位......)进行排序，依次进行，直到数组中最大数的位数排序完。

步骤：

• 先找出数组中最大数，求出位数，即需要分配的次数。
• 定义一个二维的临时数组，第一维用来存放0-9的正在分配的类别，长度为10，第二维用来从数组中提取出来的数，因为在分配前是不知道0-9各自有多少数，所以定义第二维的长度为数组的长度。
• 定义一个长度为10的数组，用来存放每次分配到二维数组时，每个维度的长度，作为下次同样类别存放的下标。
• 根据求出的分配次数进行for循环遍历，此时需要在定义一个变量n，初始为1，用来根据每次遍历分别类乘于10(比如第一次为1，、1%10得到个位数，依次类推)。
• 将得到的位数作为二维数组的第一维下标，第二维下标为上面的长度为10数组对应位数的值，用来存放当前判断的数字。
• 定义一个变量 index，用来记录取得到的数字要存放的位置，存放后的数组将覆盖原来要分配的数组。
• 使用两个for循环，用来取出二维数组里记录的数组。
• 当分配完一个类别后，要将记录数组长度的数组用到的下标归为0，用于下次的使用。

演示：

image.png

Jvav代码：

package com.company;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 45, 87, 32, 9, 7, 159, 324, 4, 107, 69,58};
        Main.base(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void base(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        //计算最大数字是几位数
        int count = (max + "").length();
        //用来临时存放数据的数组
        int[][] temp = new int[10][arr.length];
        //用于记录在temp中相应的数组中存放数字的数量
        int[] counts = new int[10];
        //根据最长长度的数决定比较次数
        for (int j = 0, n = 1; j < count; j++,n *= 10) {
            //把每个数字分别计算余数
            for (int d = 0;d<arr.length;d++){
                //计算余数
                int yu = arr[d]/n%10;
                //把当前遍历的数字存放在指定位置的数组中
                temp[yu][counts[yu]] = arr[d];
                //记录数字
                counts[yu]++;
            }
            //记录取出元素要放在原数组的位置
            int  index = 0;
            //把数组从二维数组取出来
            for (int k = 0;k<counts.length;k++){
                //判断记录的数组是否有记录
                if (counts[k]!=0){
                    //若有 则以记录该数组下标对应值为当前位数的数量
                    for (int l =0;l<counts[k];l++){
                        //取出元素
                        arr[index]=temp[k][l];
                        //移动下标
                        index++;
                    }
                    //遍历完，清空，下个位数记录需要
                    counts[k]=0;
                }
            }

        }
    }
}