算法排序-基数排序

何为基数排序？

    基数排序为非比较型排序。利用计数排序，通过比较每位数字的排序，完成整个数字排序。

基数排序比较方式

• 低位到高位排序：排序时一次计算集合中每个元素的个位、十位、千位、……进行排序。原则是数据的高位大的，数据一定大。遍历集合中最大的元素位数，位数不同时，依据最大数据长度，高位补0进行计算。
• 从高位到地位排序：首先获取高位值，位数不够的高位补0，按照高位分桶，高位相同时，每个桶中次位还需要再分桶，以此递归进行计算，直到最低位再进行排序。其他桶也是类似方式。
• 从高位到低位不是不可以实现，只是实现难度较大，一般不用。一般基数排序都是在指的从低位到高位排序。

基数排序代码地位到高位排序

package com.booby.algorithm.radix;

import com.booby.algorithm.utils.Utils;

import java.util.Arrays;

/**
 * 功能描述: 基数排序，从最低位开始 每位数采用稳定计数排序
 *
 * @author: lizt
 * @date: 2020/8/28 23:55
 **/

public class Lowest {

    public static final Integer[] arr = {4215,2403,1152,5326,3052,4308,1241};

    public static void sorted(Integer[] arr){
        // 整理数据，按照位数最多的来计算，不足则补0
        int maxLength = 4;
        for (int i = 0; i < maxLength; i++) {
            // 计算除数
            int division = (int)Math.pow(10, i);
            Integer[] count = new Integer[10];
            Arrays.fill(count, 0);
            // 计算每个数据中每位出现次数
            for (int j = 0; j < arr.length; j++) {
                int countIndex = arr[j] / division % 10;
                count[countIndex]++;
            }
            // count 累加数组
            for (int j = 1; j < count.length; j++) {
                count[j] += count[j-1];
            }
            // 还原数据
            Integer[] temp = new Integer[arr.length];
            for (int j = arr.length - 1; j >= 0; j--) {
                int index = arr[j] / division % 10;
                // 最后一位在原数组中的位置
                int tempIndex = count[index] - 1;
                temp[tempIndex] = arr[j];
                count[index]--;
            }
            // 覆盖原数组
            for (int j = 0; j < arr.length; j++) {
                arr[j] = temp[j];
            }
        }
    }
    public static void main(String[] args) {
        sorted(arr);
        Utils.print(arr);
    }
}

基数排序稳定性：

    基数排序是一种特殊的稳定的计数排序，基数排序也是稳定排序。

基数排序复杂度：