基数排序 - 算法实现 - 基数排序的代码实现

基数排序 - 算法实现 - 基数排序的代码实现

一、引言

在计算机科学的世界里，排序算法就像是一群技艺精湛的工匠，各自有着独特的“手艺”来对数据进行整理。基数排序（Radix Sort）便是其中一位别具特色的“工匠”，它不直接比较元素的大小，而是通过多轮按位排序来完成整个排序过程。这种独特的排序方式使得基数排序在处理整数数据时具有高效性，尤其是当待排序数据的位数相对固定时，其性能表现十分出色。接下来，我们将深入探究基数排序的原理、实现步骤以及代码实现。

二、基数排序的原理

基数排序的核心思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。它是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序一般有两种实现方式：LSD（Least Significant Digit first）和 MSD（Most Significant Digit first），即从最低位开始排序和从最高位开始排序，这里我们主要介绍 LSD 方式。

原理示例

假设有一组待排序的整数：[170, 45, 75, 90, 802, 24, 2, 66]。我们将使用基数排序（LSD）对其进行排序，具体步骤如下：

1. 第一轮排序（按个位）：
   • 个位数字分别为：0, 5, 5, 0, 2, 4, 2, 6。
   • 按照个位数字进行排序，得到：[170, 90, 802, 2, 24, 45, 75, 66]。
2. 第二轮排序（按十位）：
   • 十位数字分别为：7, 9, 0, 0, 2, 4, 7, 6。
   • 按照十位数字进行排序，得到：[802, 2, 24, 45, 66, 170, 75, 90]。
3. 第三轮排序（按百位）：
   • 百位数字分别为：8, 0, 0, 0, 0, 1, 0, 0。
   • 按照百位数字进行排序，得到：[2, 24, 45, 66, 75, 90, 170, 802]。

通过三轮按位排序，我们成功地将这组数据从小到大进行了排序。

三、基数排序的代码实现（Python）

def radix_sort(arr):
    # 找到数组中的最大值，确定最大位数
    max_num = max(arr)
    exp = 1
    # 从最低位开始，逐位进行排序
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    return arr
def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    # 统计每个位上数字的出现次数
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
    # 计算累计次数
    for i in range(1, 10):
        count[i] += count[i - 1]
    # 构建输出数组
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
    # 将输出数组复制回原数组
    for i in range(n):
        arr[i] = output[i]
# 测试代码
arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort(arr)
print("排序后的数组:", sorted_arr)

代码解释

1. radix_sort 函数：
   • 首先找到数组中的最大值，确定最大位数。
   • 从最低位开始，逐位调用 counting_sort 函数进行排序。
   • 每次排序后，将位数乘以 10，以便处理更高位。
2. counting_sort 函数：
   • 该函数是基数排序的核心辅助函数，用于对指定位上的数字进行计数排序。
   • 统计每个位上数字的出现次数。
   • 计算累计次数，确定每个数字在输出数组中的位置。
   • 构建输出数组，并将其复制回原数组。

四、复杂度分析

五、总结

基数排序是一种高效的排序算法，尤其适用于处理整数数据。它通过多轮按位排序，避免了直接比较元素大小，从而在一定程度上提高了排序效率。通过本文的介绍，我们了解了基数排序的原理、实现步骤以及代码实现，同时也对其复杂度有了清晰的认识。希望读者能够掌握基数排序这一实用的排序算法，并在实际应用中灵活运用。