深入理解基数排序：从原理到 Python 实现

你好！作为一名开发者，我们经常需要在处理海量数据时做出选择：是追求最坏情况下的稳定表现，还是追求线性时间的极致速度？今天，我们将深入探讨一种非基于比较的排序算法——基数排序。不同于我们熟悉的快速排序或归并排序，基数排序通过利用数字本身的内部结构（即数位），能够以接近线性的时间复杂度对整数或字符串进行排序。在这篇文章中，我们将通过 Python 代码，从零开始构建一个健壮的基数排序实现，并分享在实际开发中的一些实用技巧。

为什么选择基数排序？

首先，让我们快速回顾一下问题背景。假设你有一个包含成千上万个整数的数组，比如员工 ID、电话号码或特定的交易 ID。如果使用传统的比较型排序（如 Python 内置的 sort，通常是 Timsort），时间复杂度最好也只能达到 $O(N \log N)$。然而，基数排序通过“分而治之”的思想，按数位进行分配，可以达到 $O(d \cdot n)$ 的效率（其中 $d$ 是数字的最大位数）。当 $d$ 是常数或很小的时候，这几乎就是 $O(n)$ 的线性时间！这对处理大规模整数数据集来说是一个非常强大的工具。

算法核心原理：从个位到最高位

基数排序的核心思想非常直观。你可以把它想象成我们在整理扑克牌：

• 按面值分组：先把所有的牌按面值（花色不论）分成 13 堆。
• 按花色收集：将这 13 堆按顺序收起来，然后再按花色分成 4 堆。
• 最终收集：最后收起来的牌就是有序的。

在数字排序中，我们通常使用最低有效位优先的策略。这意味着我们先比较个位数，然后是十位数，接着是百位数，以此类推。为了保证每一轮排序后，上一轮的相对顺序不被打乱，基数排序必须依赖一个稳定的子排序算法（通常是计数排序）。

算法演示

让我们通过一个具体的例子来看看它是如何一步步工作的。我们将数组 [170, 45, 75, 90, 802, 24, 2, 66] 进行排序。

原始输入： [170, 45, 75, 90, 802, 24, 2, 66]

#### 第一轮：按个位数排序

我们只看每个数字的个位（0-9），将它们放入对应的桶中，然后按顺序收集。

• 0 (170, 90)
• 2 (802, 2)
• 4 (24)
• 5 (45, 75)
• 6 (66)

第一轮结果： [170, 90, 802, 2, 24, 45, 75, 66]
注意：虽然这一步看起来很乱，但对于个位数相同的数字（比如 170 和 90，或者 802 和 2），它们的相对顺序已经稳定了。

#### 第二轮：按十位数排序

现在，我们看第一轮结果的十位数。

• 0 (802, 2) -> 十位是 0
• 2 (24)
• 4 (45)
• 5 (75)
• 6 (66)
• 7 (170)
• 9 (90)

第二轮结果： [802, 2, 24, 45, 66, 170, 75, 90]
现在你可以看到数组越来越接近有序了。2 和 24 已经排在前面。

#### 第三轮：按百位数排序

最后，我们看百位数。

• 0 (2, 24, 45, 66, 75, 90) -> 假设不足的位数为 0
• 1 (170)
• 8 (802)

最终结果： [2, 24, 45, 66, 75, 90, 170, 802]

正如你所见，仅仅经过 3 轮处理，我们就得到了完全有序的数组。

Python 实现方式一：使用计数排序（最优化方案）

在生产环境中，为了获得最佳性能，我们通常会使用计数排序作为基数排序的子程序。这种方法不需要创建多个列表（桶），而是通过计算偏移量来直接确定元素的位置，内存利用率极高。

这是最推荐的做法，不仅速度快，而且逻辑非常严密。

def counting_sort_for_radix(arr, exp):
    """
    对数组 arr 按照 exp 指定的数位进行计数排序
    arr: 待排序数组
    exp: 1, 10, 100, ... 指定当前处理的是哪一位
    """
    n = len(arr)
    # 输出数组，用于存储排序后的结果
    output = [0] * n
    
    # 初始化计数数组，范围是 0-9
    count = [0] * 10

    # 1. 统计当前位上每个数字出现的频率
    # 例如：exp=1 时，(170 // 1) % 10 = 0，index 为 0
    for i in range(n):
        index = (arr[i] // exp) 
        count[index % 10] += 1

    # 2. 将 count[i] 变为该数字在 output[] 中的实际位置
    # 这一步是计数排序的关键，通过累加确定边界
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 3. 构建 output 数组
    # 必须从后向前遍历，以保证排序的稳定性（相同数字保持原有顺序）
    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) 
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

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

def radix_sort(arr):
    """
    基数排序主函数
    """
    if len(arr) == 0:
        return arr

    # 找出数组中最大的数字，以确定我们需要处理多少位
    max_num = max(arr)

    # 从最低位（个位）开始，对每一位进行计数排序
    # exp 每次乘以 10，依次处理个位、十位、百位...
    exp = 1
    while max_num // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10

# --- 测试代码 ---
data = [170, 45, 75, 90, 802, 24, 2, 66]
print(f"原始数组: {data}")
radix_sort(data)
print(f"排序结果: {data}")

代码深入解析

在这里，我想强调几个初学者容易困惑的细节：

• 为什么是 max_num // exp > 0？

这是我们循环的终止条件。只要 INLINECODE5d388f75 除以当前的位数 (INLINECODE206ee283) 仍然大于 0，说明还有更高位的数字需要处理。例如，802 有 3 位，当 INLINECODEbdf5b605 变成 1000 时，INLINECODE86e4d853 等于 0，循环结束。

• 为什么要从后向前遍历 (while i >= 0)？

这是为了保持稳定性。假设我们有两个数字 82 和 72，在十位数这一轮，它们都是 7（在十位上）。如果我们从头开始遍历，先处理 82，再处理 72，那么在输出数组中，72 可能会排在 82 前面，这就破坏了上一轮（个位排序）确立的顺序。反向遍历确保了先出现的元素在排序后依然排在前面。

Python 实现方式二：桶排序逻辑（更直观，易理解）

如果你觉得上面的计数排序逻辑过于复杂，或者你在面试中需要快速写出一个易于解释的版本，那么使用“桶”的方法是极好的选择。虽然它的内存开销稍微大一点点（需要创建 10 个列表），但在 Python 中，列表的动态操作非常方便，代码可读性极高。

def radix_sort_buckets(arr):
    if len(arr) == 0:
        return arr

    max_num = max(arr)
    exp = 1  # 当前处理的位数：1->个位, 10->十位, 100->百位

    while max_num // exp > 0:
        # 创建 10 个桶，对应数字 0-9
        buckets = [[] for _ in range(10)]

        # 分发过程：将数字放入对应数字的桶中
        for num in arr:
            digit_index = (num // exp) % 10
            buckets[digit_index].append(num)

        # 收集过程：按顺序从桶中取出元素，重写原数组
        # 这里使用了列表推导式来展平 buckets
        arr = [num for bucket in buckets for num in bucket]

        # 移动到下一位
        exp *= 10

    return arr

# --- 测试代码 ---
data = [170, 45, 75, 90, 802, 24, 2, 66]
print(f"原始数组: {data}")
sorted_data = radix_sort_buckets(data)
print(f"排序结果: {sorted_data}")

这种方法的优缺点

优点： 逻辑非常清晰。你实际上是在物理上把数字扔进不同的篮子里，然后再把篮子按顺序收起来。这对于解释算法原理非常有帮助。
缺点： 在 C++ 或 Java 等语言中，频繁创建和销毁对象（桶）会增加垃圾回收的压力。但在 Python 中，由于 append 操作非常高效，对于中小规模的数据集，这种方法的性能与计数排序版本相差无几，甚至有时因为减少了数学计算而更快。

实战应用与边界情况

现在我们知道了如何实现它，但在实际项目中，你可能会遇到一些特殊情况。让我们来看看如何处理这些问题。

1. 处理负数

标准的基数排序只能处理非负整数。如果你直接传入负数，上面的代码会报错或产生死循环。为了支持负数，一个通用的技巧是将数组分为正数和负数两部分。

• 负数部分：取其绝对值，进行基数排序，然后将结果反转（因为 -10 5）。
• 正数部分：正常进行基数排序。
• 最后合并：[排序后的负数] + [排序后的正数]。

def radix_sort_with_negatives(arr):
    if not arr:
        return arr

    # 将正数和负数分开
    neg_nums = [-x for x in arr if x = 0]

    # 对负数的绝对值进行排序
    radix_sort(neg_nums) # 复用上面的排序函数
    radix_sort(pos_nums)

    # 负数部分需要反转并取负，恢复为原来的负值
    # 因为绝对值越大的负数，实际值越小
    sorted_neg = [-x for x in reversed(neg_nums)]

    return sorted_neg + pos_nums

data = [170, -45, -75, 90, 802, -24, 2, 66]
print(f"含负数排序: {radix_sort_with_negatives(data)}")
# 输出: [-75, -45, -24, 2, 66, 90, 170, 802]

2. 何时应该使用基数排序？

虽然基数排序看起来很强大，但 Python 的内置 INLINECODE2b280a90 (Timsort) 已经高度优化。通常情况下，直接使用 INLINECODE17cc85db 是最快的选择。但在以下场景中，自定义的基数排序可能更优：

• 特定的数据结构：当你需要按照数字的特定属性（如 IP 地址的每一段、日期的年月日）进行排序时，基数排序的逻辑非常契合。
• 定长整数数组：如果你确定数据范围固定且位数较少（例如排序 100 万个 6 位数的 ID），基数排序的稳定性和线性时间优势会体现出来。

性能分析与优化建议

在我们结束之前，让我们聊聊性能。

• 时间复杂度：$O(d \cdot (n + b))$，其中 $d$ 是位数，$n$ 是元素数量，$b$ 是基数（这里是 10）。实际上可以看作是 $O(n)$。
• 空间复杂度：$O(n + b)$。我们需要额外的输出数组或桶空间。

优化小贴士：

如果你的数字范围很大，但是比较稀疏，我们可以考虑使用更大的基数（比如 Base 256 或 16 进制），这样可以减少循环的次数（$d$ 减小），但会增加桶的大小（$b$ 增大）。在 Python 中，使用位运算来代替除法 (INLINECODE1ab163d9 和 INLINECODE4110682c) 可以进一步提升速度，因为位运算在底层硬件上更快。

总结

在这篇文章中，我们不仅学习了基数排序的基本原理，还深入探讨了两种不同的 Python 实现方式：基于计数排序的高效版和基于桶排序的直观版。我们还解决了负数排序这一常见的面试难题。

基数排序提醒我们，有时候跳出“比较”的思维定势，利用数据本身的结构（数位），可以设计出非常优雅的算法。希望你在下次面对海量数据排序问题时，能想起这个强有力的工具。

下一步行动：

你可以尝试修改上面的代码，使其支持对字符串（如英文单词）进行字典序排序。提示：你可以将字符串看作是一个 256 进制的数字序列！

如果你对代码有任何疑问，或者想要分享你实现的优化版本，随时欢迎交流。祝编码愉快！