基数排序 #

1. 基数排序算法思想 #

基数排序（Radix Sort）基本思想：

将整数按位数切割成不同的数字，然后按每个位数分别比较进行排序。

2. 基数排序算法步骤 #

基数排序算法可以采用「最低位优先法（Least Significant Digit First）」或者「最高位优先法（Most Significant Digit first）」。最常用的是「最低位优先法」。

下面我们以最低位优先法为例，讲解一下算法步骤。

遍历数组元素，获取数组最大值元素，并取得位数。
定义一个长度为 10 的桶 buckets，分别代表 0 ~ 9 这 10 位数字。
以个位元素为索引，根据数组元素个位上的值，将数组元素存入对应数字的桶中。
清空原始数组，并从桶中依次取出对应元素，重新加入到原始数组中。
之后分别以十位，百位，…，最大值元素的最高位为索引，根据元素对应位上的数字，存入对应数字的桶中。并合并数组，完成排序。

3. 基数排序动画演示 #

初始序列为 [32, 1, 10, 96, 57, 7, 62, 47, 82, 25, 79, 5]，序列所有元素的最大位数为 2。
以个位为索引，根据元素个位上的数字，将其分别存入到 0 ~ 9 这 10 个桶中。
清空原始数组，并从桶中依次取出对应元素，重新加入到原始数组中。此时序列变为 [10, 1, 32, 62, 82, 25, 5, 96, 57, 7, 47, 79]。
以十位为索引，根据元素十位上的数字，将其分别存入到 0 ~ 9 这 10 个桶中。
清空原始数组，并从桶中依次取出对应元素，重新加入到原始数组中。此时序列变为 [1, 5, 7, 10, 25, 32, 47, 57, 62, 79, 82, 96]，完成排序。

4. 基数排序算法分析 #

时间复杂度：$O(n \times k)$。其中 $n$ 是待排序元素的个数，$k$ 是数字位数。$k$ 的大小取决于数字位的选择（十进制位、二进制位）和待排序元素所属数据类型全集的大小。
空间复杂度：$O(n + k)$。
排序稳定性：基数排序是一种 稳定排序算法。

5. 基数排序代码实现 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def radixSort(self, arr):
        # 桶的大小为所有元素的最大位数
        size = len(str(max(arr)))

        # 从低位到高位依次遍历每一位，以各个数位值为索引，对数组进行按数位排序
        for i in range(size):
            # 使用一个长度为 10 的桶来存放各个位上的元素
            buckets = [[] for _ in range(10)]
            # 遍历数组元素，根据元素对应位上的值，将其存入对应位的桶中
            for num in arr:
                buckets[num // (10 ** i) % 10].append(num)
            # 清空原始数组
            arr.clear()
            # 从桶中依次取出对应元素，并重新加入到原始数组
            for bucket in buckets:
                for num in bucket:
                    arr.append(num)

        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.radixSort(nums)