Python Radix Sort 教程: 整数、负数和浮点数排序

Python 基础排序算法：基数排序详解与示例

Python Radix Sort 教程：整数、负数和浮点数排序

Python 数字排序指南：从整数到浮点的基数排序实现

高效排序算法讲解：Python 中的基数排序应用

Python 排序算法全解析：Radix Sort 的用法与实例

Python 基数排序简介

基数排序是一种非比较型排序算法，它通过按位对数字进行排序来完成排序。与直接比较整个数字（如快速排序或归并排序）不同，基数排序将元素根据其数字或字符分配到“桶”中，然后逐位处理。

对于整数，基数排序通常从最低有效位（LSD）到最高有效位（MSD）进行排序。这样可以保证稳定性，在处理完所有位后得到有序数组。

—

基数排序的工作原理

• 找到数组中的最大值，以确定需要处理的位数。
• 对每一位（个位、十位、百位等）使用稳定排序（如计数排序）。
• 重复此过程直到处理完所有位。

示例：对数组 [170, 45, 75, 90, 802, 24, 2, 66] 进行排序：

• 按个位排序 → [170, 90, 802, 2, 24, 45, 75, 66]
• 按十位排序 → [802, 2, 24, 45, 66, 170, 75, 90]
• 按百位排序 → [2, 24, 45, 66, 75, 90, 170, 802]

此时数组已经排序完成。

—

Python 正整数基数排序实现

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    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(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    for i in range(n):
        arr[i] = output[i]


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

    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10


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

—

输出

排序后的数组: [2, 24, 45, 66, 75, 90, 170, 802]

—

支持负整数的扩展

• 将负数和非负数分开。
• 将负数取绝对值转换为正数。
• 分别对两部分应用基数排序。
• 对负数结果进行翻转（绝对值大的负数排在前面）。
• 合并负数和非负数得到最终有序数组。

def radix_sort_positive(arr):
    if not arr:
        return arr
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10


def radix_sort(arr):
    negatives = [-x for x in arr if x < 0]
    non_negatives = [x for x in arr if x >= 0]

    radix_sort_positive(negatives)
    radix_sort_positive(non_negatives)

    negatives = [-x for x in reversed(negatives)]
    return negatives + non_negatives


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

—

浮点数排序

浮点数也可以通过将它们转换为整数来使用基数排序。常用方法：

• 缩放：将所有浮点数乘以 10 的幂，将其转换为整数（适用于固定精度浮点数）。
• 位重解释：将 IEEE 754 浮点数按位当作整数处理，并对负数进行调整以保持顺序。

以下示例使用**缩放法**对正浮点数进行排序：

def radix_sort_floats(arr, precision=2):
    # 将浮点数缩放为整数
    factor = 10 ** precision
    int_arr = [int(x * factor) for x in arr]

    radix_sort(int_arr)

    # 转回浮点数
    return [x / factor for x in int_arr]


# 示例
arr = [3.14, 2.71, 1.41, 0.99, 2.0]
sorted_arr = radix_sort_floats(arr)
print("排序后的浮点数:", sorted_arr)

—

输出

排序后的浮点数: [0.99, 1.41, 2.0, 2.71, 3.14]

—

何时使用基数排序

• 当需要排序大量整数且最大值相对较小时。
• 对固定长度字符串进行高效排序。
• 在固定宽度整数或缩放浮点数的情况下需要线性时间排序。

—

局限性

• 不是通用排序算法，仅适用于整数或固定长度键。
• 需要额外的桶空间（不是原地排序）。
• 对于任意浮点数或混合类型，基于比较的排序（如 Python 内置 Timsort）更安全。

—

总结

基数排序是一种快速的按位排序算法，可以处理整数、负数和固定精度浮点数。在适用场景下，它能提供线性时间性能。通过对浮点数进行适当转换，基数排序的适用范围可以扩展到整数之外。

英文: A Complete Guide to Radix Sort in Python with Examples