Python

Question

我在 python 中使用递归编写了一个 MergeSort 程序，但我不断收到有关第 27 行、第 23 行、第 18 行的错误和一个递归错误：
"RecursionError: maximum recursion depth exceeded in comparison" 但我似乎没有在我的代码中发现任何明显的错误。

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

Python - MergeSort 递归错误

Python - MergeSort Recursion Error

sorting

algorithm

recursion

mergesort