为什么我的合并排序程序不工作？

Question

为什么我的归并排序程序不工作？

def merge(a, p, q, r):

    n1 = (q - p) + 1

    n2 = r - q

    L = [0] * n1

    M = [0] * n2

    for i in range(n1):

        L[i] = a[i]

    for j in range(n2):

        M[j] = a[j]

    i = 0

    j = 0

    for k in range(p, r):

        if L[i] <= M[j]:

            a[k] = L[i]

            i += 1

        else:

            a[k] = M[j]

            j += 1

def merge_sort(a, p, r):

    if len(a) <= 1:

        print('list has only one element')

    else:

        q = len(a) // 2

        merge_sort(a, p, q)

        merge_sort(a, q + 1, r)

        merge(a, p, q, r)

        

a = [3,41,52,26,38,57,9,49]

merge_sort(a, 0, len(a) - 1)

for _ in range(len(a)):

    print('%d', a[_])

Answer 1

您的代码中存在多个问题：切片的初始化循环不正确。索引a应该分别从p和开始q+1。将它们更改为：&nbsp; for i in range(n1):&nbsp; &nbsp; &nbsp; L[i] = a[p+i]&nbsp; for j in range(n2):&nbsp; &nbsp; &nbsp; M[j] = a[q+1+j]或者简单地写：&nbsp; L = a[p..q+1]&nbsp; M = b[q+1..r+1]这使得qandr应该被排除在外而不是被包含在内是显而易见的。合并循环不正确：范围应该是range(p, r+1)并且一旦一个临时数组用完，比较指的是超出orL[i] <= M[j]边界的元素。LMq计算不正确merge_sort：它应该是q = (p + r) // 2测试if len(a) <= 1:不正确，您应该测试切片是否至少有 2 个元素，如果没有则什么也不做：&nbsp; if p < r:&nbsp; &nbsp; &nbsp; q = (p + r) // 2&nbsp; &nbsp; &nbsp; merge_sort(a, p, q)&nbsp; &nbsp; &nbsp; merge_sort(a, q + 1, r)&nbsp; &nbsp; &nbsp; merge(a, p, q, r)这是一个排除了上限的修改版本：def merge(a, p, q, r):&nbsp; &nbsp; L = a[p..q]&nbsp; &nbsp; M = a[q..r]&nbsp; &nbsp; i = 0&nbsp; &nbsp; j = 0&nbsp; &nbsp; for k in range(p, r):&nbsp; &nbsp; &nbsp; &nbsp; if j >= len(M) or (i < len(L) and L[i] <= M[j]):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a[k] = L[i]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i += 1&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a[k] = M[j]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j += 1def merge_sort(a, p, r):&nbsp; &nbsp; if r - p > 1:&nbsp; &nbsp; &nbsp; &nbsp; q = p + (r - p) // 2&nbsp; &nbsp; &nbsp; &nbsp; merge_sort(a, p, q)&nbsp; &nbsp; &nbsp; &nbsp; merge_sort(a, q, r)&nbsp; &nbsp; &nbsp; &nbsp; merge(a, p, q, r)&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;a = [3,41,52,26,38,57,9,49]merge_sort(a, 0, len(a))for _ in range(len(a)):&nbsp; &nbsp; print('%d', a[_])