基数排序

基数排序 | Radix Sort

定义 | Definition

基数排序是一种非比较型整数排序算法，它通过按位数（从低位到高位或从高位到低位）进行多次排序来实现排序。基数排序利用了稳定排序算法（如计数排序或桶排序）作为子过程，对每一位进行排序。

Radix Sort is a non-comparative integer sorting algorithm that sorts numbers by processing individual digits. It performs multiple passes, either from the least significant digit to the most significant digit (LSD) or vice versa. Radix Sort uses a stable sorting algorithm, such as Counting Sort or Bucket Sort, as a subroutine to sort the digits.

算法步骤 | Algorithm Steps

1. 确定最大位数: 找出数组中最大元素的最大位数。 Determine the Maximum Digit Count: Find the maximum number of digits of the largest element in the array.

2. 逐位排序: 从最低有效位（LSD）到最高有效位（MSD），依次对每一位进行排序。 Sort by Each Digit: Starting from the least significant digit (LSD) to the most significant digit (MSD), sort the numbers by each digit.

3. 稳定排序: 在每一位的排序过程中，使用稳定排序算法来保持相同数字间的相对顺序。 Stable Sorting: Use a stable sorting algorithm during each digit sorting step to maintain the relative order of numbers with the same digit value.

算法实现 | Algorithm Implementation

以下是使用计数排序作为子过程的基数排序的 Python 实现：

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # 基数 | Base is 10
 
    # 计数每个数字出现的次数 | Count occurrences of each digit
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
 
    # 计算实际位置 | Compute actual positions
    for i in range(1, 10):
        count[i] += count[i - 1]
 
    # 构建输出数组 | Build the output array
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
 
    # 复制回原数组 | Copy the output array to arr
    for i in range(n):
        arr[i] = output[i]
 
def radix_sort(arr):
    # 找到最大数来决定最大的位数 | Find the maximum number to determine the maximum number of digits
    max_val = max(arr)
    exp = 1  # 从最低有效位开始 | Start with the least significant digit
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

复杂度分析 | Complexity Analysis

• 时间复杂度: 基数排序的时间复杂度为 $O(d\times (n+k))$，其中 $n$ 是数组的长度，$d$ 是最大数字的位数，$k$ 是基数（对于十进制数，$k=10$）。对于常数 $d$ 和 $k$，时间复杂度接近于 $O(n)$。 Time Complexity: The time complexity of Radix Sort is $O(d\times (n+k))$, where $n$ is the number of elements in the array, $d$ is the number of digits in the largest number, and $k$ is the base (for decimal numbers, $k=10$). For constant $d$ and $k$, the time complexity approaches $O(n)$.
• 空间复杂度: 空间复杂度主要由输出数组和计数数组决定，为 $O(n+k)$。 Space Complexity: The space complexity is mainly determined by the output and count arrays, which is $O(n+k)$.

注意事项 | Notes

1. 适用范围: 基数排序通常适用于整数排序，特别是当键值范围较小时。 Applicability: Radix Sort is typically used for sorting integers, especially when the range of keys is not large.
2. 稳定性: 基数排序依赖于稳定的子排序算法，以保证相同位值的元素顺序不变。 Stability: Radix Sort relies on a stable sub-sorting algorithm to ensure that the order of elements with the same digit value remains unchanged.
3. 基数选择: 基数的选择可以是任意正整数，但一般为 10（十进制）或 2（二进制），具体选择取决于数据的表示方式。 Radix Choice: The radix can be any positive integer, but is generally 10 (decimal) or 2 (binary), depending on the data representation.