Python - MergeSort 递归错误

Question

我在 python 中使用递归编写了一个 MergeSort 程序，但我不断收到有关第 27 行、第 23 行、第 18 行和递归错误的错误:
“RecursionError:比较时超出了最大递归深度”，但我似乎没有在我的代码中发现任何明显的错误。

def merge(list, start, middle, end):
    L = list[start:middle]
    R = list[middle:end+1]
    L.append(99999999999)
    R.append(99999999999)
    i = j = 0
    for k in range(start, end+1):
        if L[i] <= R[j]:
            list[k] = L[i]
            i += 1
        else:
            list[k] = R[j]
            j+=1

def mergesort2(list, start, end):
    if start < end:
        middle = (start + end)//2
        mergesort2(list, start, end)
        mergesort2(list, middle+1, end)
        merge(list, start, middle, end)

def mergesort(list):
    mergesort2(list, 0, len(list)-1)


mylist = [8,23,4,56,75,21,42,10,2,5]
mergesort(mylist)
print(mylist)

谢谢

Answer 1

def mergesort2(list, start, end):
    if start < end:
        middle = start + (end - start)//2
        mergesort2(list, start, middle) // notice middle instead of end.
        mergesort2(list, middle+1, end)
        merge(list, start, middle, end)

您在不减小其大小的情况下递归使用相同的列表，因此它永远不会达到基本情况。

编辑:另外，middle应该通过start + (end-start)/2来计算，而不是(start+end)/2，以避免在使用大数组时出现整数溢出错误.这是一个很好的做法。

编辑 2:进一步分析代码后，我发现输出是错误的。我已尝试更正它们，这是我的代码:

def merge(start, middle, end):
    L = l[:middle]
    R = l[middle:]
    i = j = k = 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            l[k] = L[i]
            i += 1
        else:
            l[k] = R[j]
            j+=1
        k += 1
    while i < len(L):
        l[k] = L[i]
        i += 1
        k += 1
    while j < len(R):
        l[k] = R[j]
        j += 1
        k += 1

def mergesort2(start, end):
    if start < end:
        middle = start + (end - start)//2
        mergesort2(start, middle)
        mergesort2(middle+1, end)
        merge(start, middle, end)

def mergesort(l):
    mergesort2(0, len(l)-1)


l = [8,23,4,56,75,21,42,10,2,5]
mergesort(l)
print(l)

需要注意的几点:

• 将变量名从 list 更改为 l 以避免与关键字 list 混淆。

• 将列表传递给每个函数是没有用的，因为它已经声明为全局变量。

• merge() 有一些问题。循环实际上应该从 0 开始运行，直到两个列表的长度都没有交叉。如果交叉，则只复制其余元素。

• 使用正确的 Python 拼接技术 :-p