Python中如何实现基数排序？-Python教程-PHP中文网

Python中如何实现基数排序？

下次还敢

发布： 2025-04-26 09:39:01

原创

774人浏览过

在 python 中实现基数排序可以通过以下步骤：1. 确定最大值以决定排序轮数；2. 从最低位开始，使用计数排序对每一位进行排序，直到最高位。基数排序适用于整数排序，具有稳定性和高效性，但适用性有限且需要额外的空间。

Python中如何实现基数排序？

Python 中如何实现基数排序？这个问题引出了一个有趣且高效的排序算法——基数排序（Radix Sort）。基数排序是一种非比较型的排序算法，它通过将整数按位数进行分组，然后依次排序这些分组来实现排序。让我们深入探讨一下如何在 Python 中实现基数排序，并分享一些实际经验和注意事项。

在 Python 中实现基数排序的核心在于理解其工作原理。基数排序通常用于排序整数或字符串。我们将使用整数作为示例，因为它更直观。基数排序的过程可以分为以下几个步骤：

确定最大值：首先，我们需要找到待排序数组中的最大值，因为这决定了我们需要进行多少次排序。
从最低位开始排序：我们从个位开始，对每一位进行排序，直到最高位。
使用计数排序：在每一位上，我们使用计数排序（Counting Sort）来进行排序。

让我们看一个 Python 实现的例子：

立即学习“Python免费学习笔记（深入）”；

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

    # 找到最大值以确定排序轮数
    max_num = max(arr)
    exp = 1

    while max_num // exp > 0:
        # 初始化计数数组
        count = [0] * 10
        output = [0] * len(arr)

        # 统计每一位上的数字出现的次数
        for num in arr:
            index = num // exp % 10
            count[index] += 1

        # 计算累积计数
        for i in range(1, 10):
            count[i] += count[i - 1]

        # 构建输出数组
        for i in range(len(arr) - 1, -1, -1):
            index = arr[i] // exp % 10
            output[count[index] - 1] = arr[i]
            count[index] -= 1

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

        # 移动到下一位
        exp *= 10

    return arr

# 测试代码
arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort(arr)
print(sorted_arr)  # 输出: [2, 24, 45, 66, 75, 90, 170, 802]

登录后复制

这个实现展示了基数排序的基本过程。需要注意的是，我们使用了计数排序作为基数排序的子程序，这使得整个算法的复杂度为 O(d(n + k))，其中 d 是最大数的位数，n 是数组长度，k 是计数排序的基数（通常为 10）。