算法03-基数排序

基数排序（Radix Sort）

基数排序是什么？

基数排序是一种非比较型的排序算法。它的核心思想是：按数字的每一位来排序。比如，对于整数，我们可以先按个位排序，再按十位排序，再按百位排序，直到所有位都排序完成。

基数排序的特点是：

1. 从低位到高位：先排序最低位（比如个位），再排序高位（比如十位、百位）。

2. 稳定排序：相同值的元素在排序后相对位置不变。

3. 适合整数或字符串：基数排序通常用于整数或固定长度的字符串排序。

一句话总结

基数排序是一种“按位分配再收集”的排序算法，它从数字的最低位（或最高位）开始，逐位排序，直到所有位处理完毕。

核心思想

假设你要给一堆手机号排序，你会先比较最后一位（个位），再比较前一位（十位），以此类推。基数排序就是这样：按位分组，多次分配和收集。

基数排序的步骤

基数排序的过程可以简单总结为以下几步：

1. 找到最大值：确定数组中最大的数，知道最多有多少位。

2. 按位排序：从最低位（个位）开始，依次对每一位进行排序。

3. 重复排序：对每一位排序后，更新数组，继续对下一位排序，直到最高位。

基数排序的详细过程

例子：
假设我们有一个数组：[170, 45, 75, 90, 802, 24, 2, 66]

1. 找到最大值
   最大值是 802，它有 3 位（个位、十位、百位）。所以需要处理 3 轮（个位→十位→百位）。

2. 按个位排序

• 将数组中的每个数按照个位分配到 10 个桶中（0~9）：

桶 0: 170, 090
桶 1: 
桶 2: 802, 002
桶 3: 
桶 4: 024
桶 5: 045, 075
桶 6: 066
桶 7: 
桶 8: 
桶 9: 

• 将桶中的数按顺序合并回数组：

[170, 90, 802, 2, 24, 45, 75, 66]

3. 按十位排序

• 将数组中的每个数按照十位分配到 10 个桶中（0~9）：

桶 0: 002, 802
桶 1: 
桶 2: 024
桶 3: 
桶 4: 045
桶 5: 
桶 6: 066
桶 7: 170, 075
桶 8: 
桶 9: 090

• 将桶中的数按顺序合并回数组：

[802, 2, 24, 45, 66, 170, 75, 90]

4. 按百位排序

• 将数组中的每个数按照百位分配到 10 个桶中（0~9）：

桶 0: 002, 024, 045, 066, 075, 090
桶 1: 170
桶 2: 
桶 3: 
桶 4: 
桶 5: 
桶 6: 
桶 7: 
桶 8: 802
桶 9: 

• 将桶中的数按顺序合并回数组：

[2, 24, 45, 66, 75, 90, 170, 802]

5. 排序完成

• 现在数组已经完全有序了！

Python3 代码示例

def counting_sort_for_radix(arr, exp):
    """
    对数组按某一位进行计数排序
    :param arr: 待排序数组
    :param exp: 当前位数（1 表示个位，10 表示十位，100 表示百位，以此类推）
    """
    n = len(arr)
    output = [0] * n  # 存储排序后的结果
    count = [0] * 10  # 计数数组，范围是 0~9

    # 统计当前位数的数字出现次数
    for num in arr:
        index = (num // exp) % 10  # 获取当前位的数字
        count[index] += 1

    # 计算每个数字在输出数组中的位置
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 将元素放入输出数组的正确位置
    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    # 将排序后的结果复制回原数组
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    """
    基数排序
    :param arr: 待排序数组
    """
    # 找到数组中的最大值，确定最大位数
    max_val = max(arr)

    # 从个位开始，逐位进行计数排序
    exp = 1
    while max_val // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10  # 移动到下一位（十位、百位等）

    return arr

# 示例
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("排序前:", arr)
print("排序后:", radix_sort(arr))

输出结果

排序前: [170, 45, 75, 90, 802, 24, 2, 66]
排序后: [2, 24, 45, 66, 75, 90, 170, 802]

关键特点

1. 稳定排序：相同数字的相对顺序不会改变（比如两个数字 24 和 24 会保持原顺序）。
2. 适合整数：尤其适合位数少但数据量大的整数排序（如手机号、身份证号）。
3. 分桶操作：每次按某一位的值分到 0~9 的桶中，再按顺序合并。

优缺点

优点

• 时间复杂度低（接近线性时间）。
• 稳定排序，适合多关键字排序（比如先按年龄排序，再按身高排序）。

缺点

• 需要额外空间存储桶。
• 只适用于整数（或能按位分解的数据）。

时间复杂度和空间复杂度

• 时间复杂度：(O(n \times k))
• (n) 是数据量，(k) 是最大位数。比如最大是 3 位数，则 (k=3)。
• 空间复杂度：(O(n + k))
• 需要额外的桶空间（一般用 10 个桶，每个桶最多存 (n) 个元素）。

实际应用场景

1. 电话号码排序（固定位数）。

2. 大量身份证号排序。

3. 需要多关键字排序的场景（比如先按年龄，再按工资排序）。

总结

基数排序像“流水线分拣员”，每次只看数字的某一位，分到对应的篮子里，再按顺序收集回来。虽然步骤多，但每一步都很简单，特别适合处理位数少的大规模整数！

1. 基数排序的核心是按位排序，从低位到高位逐步排序。

2. 它的时间复杂度是 O(n * k)，其中 n 是数组长度，k 是最大数的位数。

3. 基数排序适合用于整数或固定长度的字符串排序。

© 著作权归作者所有