基数排序（Radix Sort）

一、算法概述

1.1 算法分类

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。

• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

1.2 算法复杂度

1.3 相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

二、基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

• MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序。
• LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序。

2.1 算法描述

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

2.2 动图演示

分步图示说明：设有数组 array = {53, 3, 542, 748, 14, 214, 154, 63, 616}，对其进行基数排序：

在上图中，首先将所有待比较数字统一为统一位数长度，接着从最低位开始，依次进行排序。

• 按照个位数进行排序。
• 按照十位数进行排序。
• 按照百位数进行排序。

排序后，数列就变成了一个有序序列。

2.3 拓展

Radix Sort 基数排序是对计数排序的改进，该算法可以支持针对浮点、字符串等类型元素进行排序。其主要思想是将排序元素按数位分割依次排序，从而实现整体有序。其同样可以具有线性时间的性能

在对非负整数进行基数排序时，需要首先将排序元素统一为相同的数位长度，数位不足的排序元素可以添加前导零的方式实现数位长度统一对齐；然后从排序元素的最低位（个位）开始进行排序，直到完成对最高位的排序，此时即实现了对排序元素的整体排序。而对每个数位进行排序的过程则是通过（稳定的）计数排序完成的，故基数排序同样是稳定的。由于我们是从排序元素的最低位向最高位依次排序的，故这种方式被称为最低位（LSD，Least Significant Digit）法；反之，如果是从排序元素的最高位向最低位依次排序的，则被称之为最高位（MSD，Most Significant Digit）法

实际上，基数排序算法对排序元素的类型不要求一定是非负整数才可以进行，其对于字符串、浮点数等类型均可适用。其关键在于要求排序元素的数位长度统一。例如对整数排序时，如果排序元素中含有负数，则可以对排序元素均加上一个数使其全部为非负整数；如果元素类型是字符串的话，在计数排序过程中，可以直接使用该位字符对应ASCII码值进行计数，对于长度不足的字符串，可直接在其后面补0实现长度对齐。即在计数排序过程中，如果发现某位字符是为对齐所填充的0的话，则可认为其对应的ASCII码值为0进行计数，因为字符'A'所对应的ASCII码值是65，字符'0'所对应的ASCII码值是48，均比0大。这样即可保证基数排序的结果是符合字典序的

三、代码实现

/**
 * @Author: huangyibo
 * @Date: 2022/3/14 12:48
 * @Description: 基数排序
 */

public class RadixSort {

    public static void main(String[] args) {
        int[] arr = {220, 134, 0, 153, 2, 1314, 87, 2022};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        // 找出数组arr中的最大值
        int max = Arrays.stream(arr).max().getAsInt();

        //基于计算排序对元素的每个位进行排序
        //最多循环最大元素的位数，位数不够的用0进行排序
        for (int i = 10; i < max; i *= 10) {
            countSort(arr, i);
        }
    }

    /**
     * 基于计算排序对元素的每个位进行排序
     * 最多循环最大元素的位数，位数不够的用0进行排序
     * @param arr
     * @param divider
     */
    private static void countSort(int[] arr, int divider) {
        // 基数（数位的取值范围为[0,9]）
        int radix = 10;

        // 初始化计数数组count, 存储每个数位出现的次数
        int[] count = new int[radix];
        // 对计数数组各元素赋值
        for (int num : arr) {
            // arr中的元素要减去最小值，再作为新索引
            count[num / divider % radix]++;
        }

        // 计数数组变形，新元素的值是前面元素累加之和的值
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i-1];
        }

        //从后往前遍历元素，将其放在有序数组中的合适位置
        // 创建结果数组
        int[] newArray = new int[arr.length];

        for (int i = arr.length - 1; i >= 0; i--) {
            newArray[--count[arr[i] / divider % radix]] = arr[i];
        }
        //将有序数组赋值给原数组
        for (int i = 0; i < arr.length; i++) {
            arr[i] = newArray[i];
        }
    }
}

四、算法分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

参考： https://www.cnblogs.com/onepixel/articles/7674659.html

https://zhuanlan.zhihu.com/p/126116878

https://zhuanlan.zhihu.com/p/148228585