Python实现插入排序：条目数大于9时含单数字的输入排序失效

排序逻辑本身没有问题，出错的核心原因是数组元素为字符串类型，排序时执行的是字符串字典序比较，而非数值大小比较：

• 代码中A=input().split()得到的是字符串组成的列表，你注释掉的A=[int(x) for x in input().split()]才是将输入转换为整数的逻辑，未启用该代码导致所有大小判断都不符合数值规则。
• 字符串比较采用逐位对比ASCII值的规则：'10'与'2'比较时，先对比第一位字符'1'和'2'，'1'的ASCII值更小，因此会判定'10' < '2'为真，和数值比较的结果完全相反，最终排序出错。
• 过往测试用例未暴露问题的原因：
  • [9,8,...,2,1]所有元素都是单个数字字符串，字典序与数值序完全一致
  • [20,19,...,12,11]、[20,19,...,11,10]所有元素都是两位数字符串，十位数字的大小关系与数值大小关系匹配，字典序和数值序结果一致

仅需要将输入的字符串列表转换为整数列表即可，修改输入处理部分的代码：

# 原代码
A=input().split()
#A=[int(x) for x in input().split()]

# 修改为
A = [int(x) for x in input().split()]

如果需要保留原始字符串形式的输入，也可以修改排序时的判断条件，比较时转成整数：

while (j >=0 and int(key) < int(arr[j])):

N=int(input())
# 输入直接转整数列表
A = [int(x) for x in input().split()]

B_sorted=A.copy()
C= A.copy()
def inssort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while (j >=0 and key < arr[j]):
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key 
        
inssort(B_sorted)
for i in range(0,len(A)):
    for j in range(0,len(A)):
        if A[i]==B_sorted[j]:
            C[i]=j+1
            break
for x in B_sorted:
    print(x, "", end="")

注：原代码中j=j+1、i=i+1是多余写法，range循环会自动递增变量，不影响运行结果但可以直接删除。

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