Python 3基数排序算法实现问题求助（字符串处理方式）

安全阿岳

2026-6-12

基数排序（字符串实现）排错求助

我是编程新手，尝试用字符串处理替代取模运算符实现基数排序（Radix Sort），但运行结果不符合预期，无法完成正确排序。

原代码运行后输出：[790, 123, 122, 458, 457, 456, 0, 0, 789, 791]，完全不符合排序要求。

原代码

#use list of numbers to sort
Mylist = [122,123,124,125,456,457,458,789,790,791]
#define empty spaces using s0-9
print(Mylist)
s0 = 0
s1 = 0
s2 = 0
s3 = 0
s4 = 0
s5 = 0
s6 = 0
s7 = 0 
s8 = 0
s9 = 0
#function for getting a digit
def getDigit(num, loc):
    digits = [int(digit) for digit in str(num)]
    return(digits[loc-1])

#function for radix sorting a list
def radix(l):
    if type(l) is not list:
        print("ERR: The variable is not a list")
        return
    for i in l:
        print(i, l.index(i))
    print("initiating LSD identification")
    SetDigitValues(l, 1)

#function for assigning numbers in a list to s0-9, lining by LSD first
def SetDigitValues(l, j):
    #check if least significant digit location is valid 
    if j < 1:
        print("ERR: SetDigitValues was provided an invalid second element (least significant digit)")
        return
    #check if list was valid
    if type(l) is not list:
        print("ERR: The variable is not a list")
        return
    #define all used elements outside of function so it can see and change them
    global s0
    global s1
    global s2
    global s3
    global s4
    global s5
    global s6
    global s7
    global s8
    global s9
    s0=0
    s1=0
    s2=0
    s3=0
    s4=0
    s5=0
    s6=0
    s7=0
    s8=0
    s9=0
    #get digit of specified integer using the digit location, sorting into s0-9
    for i in l:
        if getDigit(i, (len(str(i)) + 1) - j) == 0:
            s0 += 1
        elif getDigit(i, (len(str(i)) + 1)-j) == 1:
            s1 += 1
        elif getDigit(i, (len(str(i)) + 1)-j) == 2:
            s2 += 1
        elif getDigit(i, (len(str(i)) + 1)-j) == 3:
            s3 += 1
        elif getDigit(i, (len(str(i)) + 1)-j) == 4:
            s4 += 1
        elif getDigit(i, (len(str(i)) + 1)-j) == 5:
            s5 += 1
        elif getDigit(i, (len(str(i)) + 1)-j) == 6:
            s6 += 1
        elif getDigit(i, (len(str(i)) + 1)-j) == 7:
            s7 += 1
        elif getDigit(i, (len(str(i)) + 1)-j) == 8:
            s8 += 1
        elif getDigit(i, (len(str(i)) + 1)-j) == 9:
            s9 += 1
    #add s0-9 so that no list locations overlap
    s1 = s0 + s1
    s2 = s1 + s2
    s3 = s2 + s3
    s4 = s3 + s4
    s5 = s4 + s5
    s6 = s5 + s6
    s7 = s6 + s7
    s8 = s7 + s8
    s9 = s8 + s9
    #make a new list to put new numbers in
    newlist = []
    h = 0
    while h < s9:
        newlist.append(0)
        h+=1
    #detect what number goes where in list using s0-9 identifications
    for g in l:
        if getDigit(g, (len(str(g)) + 1) - j) == 0:
            newlist.pop(s0-1)
            newlist.insert(s0-1, g)
            s0-=1
        elif getDigit(g, len(str(g))-j) == 1:
            newlist.pop(s1-1)
            newlist.insert(s1-1, g)
            s1-=1
        elif getDigit(g, len(str(g))-j) == 2:
            newlist.pop(s2-1)
            newlist.insert(s2-1, g)
            s2-=1
        elif getDigit(g, len(str(g))-j) == 3:
            newlist.pop(s3-1)
            newlist.insert(s3-1, g)
            s3-=1
        elif getDigit(g, len(str(g))-j) == 4:
            newlist.pop(s4-1)
            newlist.insert(s4-1, g)
            s4-=1
        elif getDigit(g, len(str(g))-j) == 5:
            newlist.pop(s5-1)
            newlist.insert(s5-1, g)
            s5-=1
        elif getDigit(g, len(str(g))-j) == 6:
            newlist.pop(s6-1)
            newlist.insert(s6-1, g)
            s6-=1
        elif getDigit(g, len(str(g))-j) == 7:
            newlist.pop(s7-1)
            newlist.insert(s7-1, g)
            s7-=1
        elif getDigit(g, len(str(g))-j) == 8:
            newlist.pop(s8-1)
            newlist.insert(s8-1, g)
            s8-=1
        elif getDigit(g, len(str(g))-j) == 9:
            newlist.pop(s9-1)
            newlist.insert(s9-1, g)
            s9-=1
    print(s9)
    print(newlist)
    

radix(Mylist)

问题排查与修复

1. 数字位索引不一致

在SetDigitValues函数填充newlist时，仅0的判断用了(len(str(g)) + 1) - j，其余数字的判断都写成了len(str(g))-j，导致取到错误的数字位，直接打乱排序逻辑。

修复：将所有数字判断的getDigit参数统一为(len(str(g)) + 1) - j。

2. 仅执行一轮排序

当前radix函数只调用了一次SetDigitValues(l, 1)，仅按最低位排序了一次。基数排序需要从最低位到最高位依次处理所有位数，才能完成完整排序。

修复：找到列表中最大数的位数，循环执行多轮排序，每轮处理更高一位，并将上一轮排序后的列表作为下一轮输入。

3. 全局变量滥用

使用全局变量s0-s9会导致状态混乱，多轮排序时极易出错，建议改为函数内部的局部变量存储计数。

4. 列表操作效率低且易出错

用pop和insert操作列表不仅性能差，还容易出现索引越界，建议直接通过索引赋值完成新列表填充。

修复后的代码

Mylist = [122, 123, 124, 125, 456, 457, 458, 789, 790, 791]
print("原列表:", Mylist)

def get_digit(num, digit_pos):
    # digit_pos从1开始，1代表最低位，补前导零统一位数
    num_str = str(num).zfill(len(str(max(Mylist))))
    return int(num_str[-digit_pos])

def radix_sort(lst):
    if not isinstance(lst, list):
        print("ERR: 输入不是列表")
        return
    
    max_num = max(lst)
    max_digits = len(str(max_num))
    current_list = lst.copy()
    
    for digit_pos in range(1, max_digits + 1):
        # 初始化计数桶
        count = [0] * 10
        # 统计每个数字出现次数
        for num in current_list:
            d = get_digit(num, digit_pos)
            count[d] += 1
        
        # 计算前缀和，确定每个数字的位置范围
        for i in range(1, 10):
            count[i] += count[i-1]
        
        # 从后往前遍历保证排序稳定性
        new_list = [0] * len(current_list)
        for num in reversed(current_list):
            d = get_digit(num, digit_pos)
            count[d] -= 1
            new_list[count[d]] = num
        
        current_list = new_list
        print(f"第{digit_pos}轮排序后:", current_list)
    
    return current_list

sorted_list = radix_sort(Mylist)
print("最终排序结果:", sorted_list)

修复说明

统一数字位获取：用zfill补前导零，确保所有数字位数一致，避免索引计算错误。
多轮排序：根据最大数的位数循环处理每一位，从最低位到最高位完成完整排序。
局部计数变量：用列表count替代全局变量，避免状态混乱。
稳定排序实现：从后往前遍历原列表，通过前缀和直接赋值到新列表，保证排序稳定性，同时避免pop/insert的错误。

运行修复后的代码，输出结果符合预期：

原列表: [122, 123, 124, 125, 456, 457, 458, 789, 790, 791]
第1轮排序后: [790, 791, 122, 123, 124, 125, 456, 457, 458, 789]
第2轮排序后: [122, 123, 124, 125, 456, 457, 458, 789, 790, 791]
第3轮排序后: [122, 123, 124, 125, 456, 457, 458, 789, 790, 791]
最终排序结果: [122, 123, 124, 125, 456, 457, 458, 789, 790, 791]

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

Python 3基数排序算法实现问题求助（字符串处理方式）

原代码 #

问题排查与修复 #

1. 数字位索引不一致 #

2. 仅执行一轮排序 #

3. 全局变量滥用 #

4. 列表操作效率低且易出错 #

修复后的代码 #

修复说明 #

原代码