基数排序（Radix Sort）原理与实现

基数排序是一种非比较型的整数排序算法，它通过逐位处理数字的每一位来实现排序。该算法将整数按位数切割成不同的数字，然后按每个位数分别进行比较和排序。基数排序适用于整数或字符串这类有固定位数的数据。

算法原理
基数排序的核心思想是"按位排序"，从最低有效位（LSF）到最高有效位（MSF）依次进行排序。每次排序都需要使用稳定的排序算法（通常使用计数排序），以保证前一次排序的结果不会被破坏。

具体步骤

1. 确定最大数字的位数：首先找出数组中最大的数字，确定其位数d，这决定了需要排序的轮数。

2. 从最低位开始排序：从个位（最低有效位）开始，依次对十位、百位...直到最高位进行排序。

3. 使用稳定的排序算法：对每一位进行排序时，必须使用稳定的排序算法（如计数排序），这样才能保证相同位数的数字能够保持之前的相对顺序。

4. 重复直到最高位：重复步骤2-3，直到处理完所有位数。

计数排序辅助过程
基数排序通常使用计数排序作为子排序算法：

1. 统计每个数字出现的次数
2. 计算前缀和，确定每个数字的最终位置
3. 从后往前遍历原数组，将元素放到正确位置

时间复杂度分析

• 最佳情况：O(d×(n+k))，其中d是最大位数，n是元素个数，k是基数（通常为10）
• 最坏情况：O(d×(n+k))
• 平均情况：O(d×(n+k))

空间复杂度
需要额外的O(n+k)空间来存储中间结果。

代码实现（Python）

def radix_sort(arr):
    # 找出最大值确定位数
    max_val = max(arr)
    exp = 1  # 从个位开始
    
    # 使用计数排序进行基数排序
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # 0-9十个数字
    
    # 统计每个数字出现的次数
    for i in range(n):
        index = (arr[i] // 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]

# 测试示例
arr = [170, 45, 75, 90, 2, 802, 24, 66]
radix_sort(arr)
print("排序结果:", arr)  # 输出：[2, 24, 45, 66, 75, 90, 170, 802]

算法特点

• 稳定性：基数排序是稳定的排序算法
• 适用性：特别适合整数排序，特别是位数不多的整数
• 局限性：不适合浮点数排序，需要额外的内存空间

基数排序通过巧妙的位处理机制，避免了比较排序的O(nlogn)下限，在特定场景下具有很好的性能表现。