如何将基数排序时间复杂度从O(N²)优化至O(N)并改写嵌套循环？

首先明确：你的基数排序代码出现O(N²)复杂度是实现错误导致的，不是算法本身的问题。基数排序的理论时间复杂度是O(d*N)，其中d是排序关键字的位数，当d是固定常数（比如分数是0-100，d=3）时，复杂度就是O(N)级别。

原代码的核心问题 #

1. num_digits计算错误：你直接把最大分数值当成了循环次数，比如最大分数是100，就会循环100次，这直接导致复杂度飙升到O(N*M)（M是最大分数值），变成平方级。正确做法是计算最大分数的位数，比如100的位数是3，只需要循环3次。
2. __flatten函数效率低下：用reduce(lambda x,y:x+y, A)拼接列表，每次拼接都会生成新列表，多次操作后总复杂度会达到O(N²)，换成extend方法可以把扁平化的时间降到O(N)。

能不能把嵌套循环改成单循环？ #

不行，这是基数排序的固有逻辑决定的：必须逐位（个位、十位、百位...）对元素进行分桶和合并，外层循环处理每一位，内层循环遍历元素分桶，这两步缺一不可。但外层循环的次数是固定常数（比如分数最多3位），所以整体复杂度依然是线性的，没必要强行改成单循环。

修正后的O(N)级实现代码 #

def __flatten(buckets):
    flattened = []
    for bucket in buckets:
        flattened.extend(bucket)
    return flattened

def radxsrt(arr, num_digits):
    for digit in range(num_digits):
        buckets = [[] for _ in range(10)]
        divisor = 10 ** digit
        for item in arr:
            # 提取当前处理位的数字
            digit_val = (item[2] // divisor) % 10
            buckets[digit_val].append(item)
        arr = __flatten(buckets)
    return arr

def get_digit_count(num):
    # 计算数字的位数
    if num == 0:
        return 1
    count = 0
    while num > 0:
        count += 1
        num = num // 10
    return count

def radx(input_list):
    max_score = max(item[2] for item in input_list)
    num_digits = get_digit_count(max_score)
    return radxsrt(input_list, num_digits)

# 使用示例
results = [['AAA', 'AAA', 65], ['AAA', 'AAB', 82], ['BBB', 'BBB', 9], ['CCC', 'CCC', 100]]
top10matches = radx(results)

优化说明 #

• 修正了位数计算逻辑，外层循环次数从“最大分数值”变成“最大分数的位数”，比如分数范围0-100时只循环3次。
• 用extend扁平化桶列表，避免了多次列表拷贝的额外开销。
• 整体时间复杂度为O(d*N)，d是常数，所以实际是线性O(N)级别。

内容的提问来源于stack exchange，提问作者theuppercaseguy