基数排序（Radix Sort）的详细实现与优化

基数排序是一种非比较型整数排序算法，其核心思想是将整数按位数逐位排序，从最低有效位（LSB）到最高有效位（MSB）依次进行。基数排序的时间复杂度为O(d*(n+k))，其中d是最大数字的位数，n是元素个数，k是基数（例如十进制中k=10）。接下来，我将逐步讲解基数排序的原理、实现细节和优化策略。

1. 基数排序的基本原理

基数排序基于“分配”和“收集”的过程：

• 分配：根据当前位的值，将元素分配到对应的桶（bucket）中。
• 收集：按桶的顺序依次将元素收集回原数组。
• 重复以上步骤，从最低位到最高位处理每一位。

2. 算法步骤（以十进制为例）

假设待排序数组为 [170, 45, 75, 90, 2, 802, 24, 66]，最大数字为802（3位数）：

1. 按个位排序：

   • 分配：根据个位数字（0-9）分配到10个桶中：
     • 桶0: 170, 90
     • 桶2: 2, 802
     • 桶4: 24
     • 桶5: 45, 75
     • 桶6: 66
   • 收集：按桶0到桶9的顺序收集元素，得到 [170, 90, 2, 802, 24, 45, 75, 66]。

2. 按十位排序：

   • 分配：根据十位数字分配（不足十位视为0）：
     • 桶0: 2, 802
     • 桶2: 24
     • 桶4: 45
     • 桶6: 66
     • 桶7: 170, 75
     • 桶9: 90
   • 收集：得到 [2, 802, 24, 45, 66, 170, 75, 90]。

3. 按百位排序：

   • 分配：根据百位数字分配：
     • 桶0: 2, 24, 45, 66, 75, 90
     • 桶8: 802
     • 桶1: 170
   • 收集：最终有序数组为 [2, 24, 45, 66, 75, 90, 170, 802]。

3. 关键实现细节

3.1 确定最大位数

需要先遍历数组找到最大值，计算其位数：

max_val = max(arr)
d = len(str(max_val))  # 十进制位数

3.2 桶的表示与收集

• 使用一个长度为k（基数）的桶列表，每个桶是一个动态数组（如列表）。
• 每次分配后，按桶顺序覆盖原数组。

3.3 处理负数（扩展）

若数组包含负数，需分开处理正负数组：

• 将负数取绝对值排序，再反转后加负号。
• 或使用偏移量将所有数转为非负数（例如加上最小负数的绝对值）。

4. 代码实现（Python）

def radix_sort(arr):
    if not arr:
        return arr
    
    # 确定最大位数
    max_val = max(arr)
    exp = 1  # 从个位开始
    base = 10  # 十进制基数
    
    while max_val // exp > 0:
        # 初始化10个桶
        buckets = [[] for _ in range(base)]
        
        # 分配阶段：根据当前位放入桶
        for num in arr:
            digit = (num // exp) % base
            buckets[digit].append(num)
        
        # 收集阶段：按桶顺序覆盖原数组
        arr.clear()
        for bucket in buckets:
            arr.extend(bucket)
        
        exp *= base  # 处理下一位
    
    return arr

5. 优化策略

5.1 基数选择优化

• 基数k的选择影响效率：k较大时（如2^16），位数d减少，但桶数增加，可能浪费内存。
• 平衡原则：通常取k≈√n，使d和k均接近O(√n)。

5.2 计数排序作为子程序

• 使用计数排序（稳定）替代桶分配，避免动态数组操作：
  1. 计算当前位每个数字的出现次数。
  2. 计算前缀和以确定位置。
  3. 从右向左扫描原数组，放入临时数组（保证稳定性）。

优化后代码示例：

def radix_sort_optimized(arr):
    if not arr:
        return arr
    
    max_val = max(arr)
    exp = 1
    base = 10
    n = len(arr)
    output = [0] * n
    
    while max_val // exp > 0:
        count = [0] * base
        
        # 统计当前位各数字出现次数
        for num in arr:
            digit = (num // exp) % base
            count[digit] += 1
        
        # 计算前缀和
        for i in range(1, base):
            count[i] += count[i-1]
        
        # 从右向左放置元素（保证稳定性）
        for i in range(n-1, -1, -1):
            digit = (arr[i] // exp) % base
            output[count[digit]-1] = arr[i]
            count[digit] -= 1
        
        # 将结果复制回原数组
        arr[:] = output
        exp *= base
    
    return arr

5.3 处理负数

若数组包含负数，可先分离正负数组：

def radix_sort_with_negatives(arr):
    negatives = [-x for x in arr if x < 0]
    positives = [x for x in arr if x >= 0]
    
    sorted_negatives = [-x for x in radix_sort_optimized(negatives)[::-1]]
    sorted_positives = radix_sort_optimized(positives)
    
    return sorted_negatives + sorted_positives

6. 复杂度分析

• 时间复杂度：O(d*(n+k))，其中d为最大位数，k为基数。当d为常数且k=O(n)时，复杂度为线性O(n)。
• 空间复杂度：O(n+k)（用于桶或计数数组）。
• 稳定性：基数排序是稳定的（关键于按位排序时需使用稳定子算法）。

7. 应用场景

• 适用：整数或字符串排序（位数有限）。
• 不适用：浮点数或位数差异极大的数据（如1和10^9混合）。

通过以上步骤，基数排序将排序问题转化为多轮稳定的分配与收集过程，结合计数排序优化后可高效处理大规模整数排序。