手写算法并记住它：基数排序

在算法的世界里，排序是基础且核心的操作之一。从简单的冒泡排序到复杂的快速排序、归并排序，每种排序算法都有其独特的适用场景和性能特点。今天，我们将聚焦于一种非比较型的整数排序算法——基数排序（Radix Sort），通过手写实现来深入理解其工作原理，并探讨如何将其记住并灵活运用。

基数排序的基本原理

基数排序是一种基于“分配”和“收集”操作的排序算法，它通过将整数按位数切割成不同的数字，然后按每个位数分别比较，从而实现排序。基数排序的关键在于其利用了整数的位权特性，从最低位（LSD，Least Significant Digit）或最高位（MSD，Most Significant Digit）开始，依次对每一位进行排序，最终得到一个有序序列。

分配与收集

基数排序的核心操作是“分配”和“收集”。分配是指将待排序的元素根据当前位的数值分配到不同的桶中；收集则是将各个桶中的元素按顺序重新组合成一个序列。这一过程需要重复进行，直到处理完所有位数。

稳定性

基数排序是一种稳定的排序算法，即相等的元素在排序后不会改变其相对顺序。这一特性使得基数排序在需要保持原始数据顺序的场景中尤为有用。

手写基数排序算法

为了更好地理解基数排序，我们将通过手写一个简单的基数排序算法来演示其实现过程。这里我们以处理非负整数为例，从最低位开始排序。

算法步骤

1. 确定最大位数：首先，我们需要找出待排序数组中的最大数，以确定需要处理的位数。
2. 初始化桶：根据基数的选择（通常是10，因为我们是十进制数），初始化10个桶（0-9）。
3. 分配元素：从最低位开始，根据当前位的数值将元素分配到对应的桶中。
4. 收集元素：按桶的顺序（0-9）将元素重新收集到一个新的数组中。
5. 重复处理：对更高一位重复步骤3和4，直到处理完所有位数。

代码实现

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # 0-9的桶
    # 统计每个桶中的元素数量
    for i in range(n):
        index = (arr[i] // 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):
    # 找出数组中的最大数，确定最大位数
    max_num = max(arr)
    exp = 1  # 从最低位开始
    while max_num // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10  # 处理更高一位
# 示例
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("排序后的数组:", arr)

代码解析

• counting_sort_for_radix函数实现了对当前位的计数排序。它首先统计每个桶中的元素数量，然后计算累积和以确定元素的最终位置，最后从后向前遍历数组以保证稳定性。
• radix_sort函数是基数排序的主函数。它首先找出数组中的最大数以确定最大位数，然后从最低位开始，对每一位调用counting_sort_for_radix函数进行排序。

如何记住基数排序

要记住基数排序，关键在于理解其“分配”和“收集”的核心思想，以及如何通过位权特性进行排序。以下是一些建议：

1. 动手实践：通过手写代码实现基数排序，加深对其工作原理的理解。
2. 可视化过程：在纸上或使用工具绘制基数排序的分配和收集过程，帮助直观理解。
3. 对比其他排序：将基数排序与其他排序算法（如快速排序、归并排序）进行对比，理解其适用场景和性能特点。
4. 应用场景思考：思考基数排序在实际问题中的应用，如电话号码排序、IP地址排序等。

结论

基数排序是一种高效且稳定的排序算法，尤其适用于整数排序场景。通过手写实现基数排序，我们不仅深入理解了其工作原理，还掌握了如何将其应用于实际问题中。记住基数排序的关键在于理解其“分配”和“收集”的核心思想，以及如何通过位权特性进行排序。希望本文的详细解析和代码实现能帮助你更好地掌握基数排序，并在未来的开发中灵活运用。