线性时间非比较类排序之基数排序

基数排序

基数排序是桶排序的扩展，因此又称“桶子法”，它是通过键值的部分信息，将要排序的元素分配至某些“桶”中，以达到排序的作用。

1. 算法思想

将各元素按位数切割成不同的数字，然后分别根据每个位数的比较结果进行排序。

2. 算法步骤

确定待排序序列的最大位数。
将所有待排序元素统一为最大数位长度（左补0）。
从最低位到最高位分别进行排序。
当最高位排序完成后，原数组变成有序序列。

3.算法分析

基数排序的执行效率非常高。我们要做的仅仅是把原始数据项从数组复制到链表中，然后再复制回去。如果待排序序列有10个数据项和 5个数位，则只需要10×2×5=100次复制：如果待排序序列有 100个数据和5个数位，则需要100×2×5=1000次复制⋯⋯复制次数和数据项的个数成正比，即O（n）。这简直就是最高效率的排序算法。
但是，当数据项增加 10倍时，一切就不一样了。关键字必须增加一位，多了一轮排序。复制的次数和数据项的个数与关键字长度成正比，可以认为关键字的长度是n的对数，因此在大多数情况下，基数排序的执行效率倒退为 $O(nlog_2 n)$ ，和快速排序差不多。
快速排序参考这篇文章
空间复杂度很好算，它是在分配元素时使用的桶空间，即10n，达此全间复杂度为O(n)。

4.算法代码

算法代码如下：
Python

# -*- coding: utf-8 -*-

# 基数排序
def radix_sort(arr) :
    maximum = max (arr) # 确定待排序数组中的最大位数
    d = 0 #d 为最大位数，初始为0
    while maximum != 0: # != ——不等于
        maximum = maximum // 10
        d += 1
    for i in range(d): # d轮排序
        s = [[] for k in range(10)] # 因为每一位数字都是0~9，所以建10个桶
        for j in arr:
            s[int(j /(10 ** i))%10].append(j) # 从个位数开始逐一进行分桶排序
        arr = [a for b in s for a in b] # 用10个桶回填原数组
    return arr

# 调用 radix-sort函数
print(radix_sort([34, 21, 13, 2, 5, 1,55,3, 1, 8]))

Java

  public static List<Integer> radixSort(List<Integer> arr) {
        int maximum = findMax(arr); // 确定待排序数组中的最大值
        int d = 0; // d 为最大位数，初始为0

        while (maximum != 0) {
            maximum /= 10;
            d++;
        }

        for (int i = 0; i < d; i++) { // d轮排序
            List<List<Integer>> buckets = new ArrayList<>();
            for (int k = 0; k < 10; k++) {
                buckets.add(new ArrayList<>());
            }

            for (int j : arr) {
                int digit = getDigit(j, i);
                buckets.get(digit).add(j);
            }
            arr = new ArrayList<>(); // 使用新的 ArrayList 替换旧的，以避免 UnsupportedOperationException
            for (List<Integer> bucket : buckets) {
                arr.addAll(bucket);
            }

        }

        return arr;
    }

    private static int findMax(List<Integer> arr) {
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            max = Math.max(max, num);
        }
        return max;
    }

    private static int getDigit(int number, int index) {
        int digit = number / (int) Math.pow(10, index);
        digit %= 10;
        return digit;
    }

        @Test
        void contextLoads () {
            List<Integer> arr = List.of(34, 21, 13, 2, 5, 1, 55, 3, 1, 8);
            arr = radixSort(arr);
            System.out.println(arr);
        }