Python实现merge sort报列表索引越界、输出结果不正确如何解决

错误汇总 #

• 临时列表b初始化为空，Python不支持对空列表直接用索引赋值，触发list assignment index out of range报错
• 多处缩进不符合Python语法规范：mergeSort函数内的分支逻辑、merge函数内的指针递增逻辑和剩余元素处理分支、输入阶段的for循环都存在缩进错位
• 左半区剩余元素写入逻辑错误：原代码else分支内错误递增右指针j，实际应递增左指针i，会导致死循环
• 双指针比对循环内的写入位置递增逻辑位置错误，原代码将指针移动逻辑写在了循环外，无法正确匹配临时列表的写入位置

修正后可运行代码 #

def mergeSort(a, l, r):
    if l < r:
        mid = (l + r) // 2
        mergeSort(a, l, mid)
        mergeSort(a, mid + 1, r)
        merge(a, l, mid, r)

def merge(a, l, mid, r):
    b = []
    i = l
    j = mid + 1
    # 双指针比对合并两个有序区间
    while i <= mid and j <= r:
        if a[i] < a[j]:
            b.append(a[i])
            i += 1
        else:
            b.append(a[j])
            j += 1
    # 追加左半区剩余元素
    while i <= mid:
        b.append(a[i])
        i += 1
    # 追加右半区剩余元素
    while j <= r:
        b.append(a[j])
        j += 1
    # 将合并结果写回原数组对应区间
    for k in range(len(b)):
        a[l + k] = b[k]

a = []
n = int(input("输入元素数量："))
print("请依次输入元素")
for i in range(0, n):
    element = int(input())
    a.append(element)

print("原始数组：", a)
mergeSort(a, 0, len(a) - 1)
print("排序后数组：", a)

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