10、基数排序（Radix Sort）

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

10.1 算法描述

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

10.2 动图演示

10.3 代码实现

import java.util.ArrayList;

/**
 * @author cai-xiansheng
 * @Description 基数排序
 * @create 2021-01-17 22:38
 */
public class RadixSort {

    /**
     * 都是：n*k (k桶的数量)
     * @param arr
     */
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        int max = arr[0];
        for (int i = 1; i < arr.length; i++)
            max = Math.max(max, arr[i]);
        int maxDigit = 0;
        while (max != 0) {
            maxDigit++;
            max /= 10;
        }
        // mod、div用来计算当前位的值，mod用来取余，然后div用来做除法。(arr[i] % mod) / div
        int mod = 10, div = 1;
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            bucketList.add(new ArrayList<>());
        // 用来循环最大值的位数，从小到大
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            // 用来分别添加到桶当中。
            for (int j = 0; j < arr.length; j++) {
                // 计算哪个桶
                int num = (arr[j] % mod) / div;
                // 在对应的桶中添加元素
                bucketList.get(num).add(arr[j]);
            }
            int index = 0;
            // 这儿用来将桶里面的元素添加到数组中
            // 循环桶
            for (int j = 0; j < bucketList.size(); j++) {
                // 循环桶里面的
                for (int k = 0; k < bucketList.get(j).size(); k++)
                    arr[index++] = bucketList.get(j).get(k);
                bucketList.get(j).clear();
            }
        }
    }

}

10.4 算法分析

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

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