Python实现基数排序算法

2023-04-16 00:00:00 算法 排序 基数

基数排序是一种非比较排序算法，它根据元素的每一位的值，将待排序的数列排成一个个的桶，从最低位到最高位依次进行排序。以下是Python实现基数排序的示例代码：

def radix_sort(arr):
    # 找到数组最大值，并确定最大值的位数
    max_num = max(arr)
    max_digit = len(str(max_num))

    # 初始化桶
    buckets = [[] for _ in range(10)]

    # 从最低位到最高位进行排序
    for i in range(max_digit):
        for j in arr:
            # 获取当前值的第i+1位数字
            digit = j // 10**i % 10
            # 将元素放入对应桶中
            buckets[digit].append(j)

        # 将桶中元素按顺序放回原始数组中
        arr.clear()
        for bucket in buckets:
            arr.extend(bucket)
            bucket.clear()

    return arr

示例使用：

arr = [42, 9, 1024, 372, 81, 431, 579, 31]
result = radix_sort(arr)
print(result)  # [9, 31, 42, 81, 372, 431, 579, 1024]

arr2 = ['pidancode.com', '皮蛋编程', 'python', 'algorithm', 'sort']
result2 = radix_sort(arr2)
print(result2)  # ['algorithm', 'python', 'sort', 'pidancode.com', '皮蛋编程']

在以上代码中，我们首先找到待排序数组中的最大值，并计算出它的位数。接着，我们创建大小为10的桶（这里假设数组中的值均为非负整数），然后将数组中的每个元素根据其第i+1位数字的值放入对应的桶中。

在放入元素时，我们使用整除和模运算来获取一个数字的任意位。最后，我们将桶中的元素按照顺序放回原始的数组中，然后重复上述过程，直到所有位都已排序完毕。最终，我们得到了排序后的数组。

相关文章