Python中的合并排序-运行时错误:超过了最大递归深度

Question

我正在使用Python进行合并排序。

我已经勾选了< code >合并功能。阵列融合得很好。

但在mergeSort函数中，将出现错误：---

RuntimeError:超过最大递归深度。

运行时错误回溯（最近一次调用）在 （） 63 打印（arr[i]）， 64 ---

在合并排序（arr，l，r）53 m=l（r-1）/2 54合并排序（ar，l，m）---

可能的原因是什么？

def merge(arr,l,m,r):
    n1 = m-l+1
    n2 = r-m

    L = [0] * n1
    R = [0] * n2

    print("First List")
    for i in range(0,n1):
        L[i] = arr[i+l]
        print(L[i]), 


    print("")
    print("Second List")    
    for j in range(0,n2):
        R[j] = arr[j+m+1]
        print(R[j]),



    #Merging the temp arrays
    i = 0
    j = 0
    k = 0
    print("")
    print("Merged List ---------->")

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            print(arr[k]),
            i+=1
        else:
            arr[k] = R[j]
            print(arr[k]),
            j+=1
        k+=1

    while i<n1:
        arr[k] = L[i]
        i+=1
        k+=1

    while j<n2:
        arr[k] = R[j]
        print(arr[k])
        j+=1
        k+=1

def mergeSort(arr,l,r):
    if l<r:
        m = l+(r-1)/2
        mergeSort(arr,l,m)
        mergeSort(arr,m+1,r)
        merge(arr,l,m,r)


arr = [0,12,13,0,1,22]
n = len(arr)

mergeSort(arr,0,n-1)
print(" ")
print("Sorted Array is")
for i in range(0,n-1):
    print(arr[i])

Answer 1

这是因为当您调用合并排序函数时，您传递的是 l = 0 和 r= 列表长度。无论你在每种情况下的计算结果如何，你 l 都将小于 r。

 m = l+(r-1)/2

Answer 2

< li >你犯了最基本的错误。Python是动态类型语言 < li >在解释为什么会出现运行时递归错误之前，您需要做一个更改。< br >不要写< code>m = l (r-1)/2，而要写< code>m = (l r)/2
因为当您调用< code>mergeSort(arr，0，n-1)时，< code>n-1是最后一个索引值，这就是为什么在< code>m = l (r-1)/2中不需要< code>r-1的原因

现在来的主要问题，为什么你得到的是，这就是答案。

• 当你在做操作像

m=（l r）/2

除法运算将给出小数部分，即 m 将被视为浮动变量，
因此 m 永远不会为 0，它将是任何浮点数，例如 0.123 或 2.122 或 1.0025

由于浮点数为 m 永远不会为 0，if 条件如果 l

您希望m为整数，而不是浮点，因此不要使用m=（l r）/2

写 m=（l r）//2 地板除法运算符 （//） 会给你整数值，你的 mergeSort（） 函数不会进入无限循环

这次您的代码将在没有任何错误的情况下执行，只需进行一次更改m=（l r）//2

但是但是但是你的合并（）函数算法不好，它没有给出排序数组，数据丢失，其他东西被打印出来

Answer 3

在 mergeSort 中计算 m 的方式是错误的（你需要将整个表达式的一半除以，而不仅仅是 （r-1））。将其更改为：

m = (l+(r-1))/2

当您计算错误时，您的方法一次又一次地递归调用自己，直到超过最大方法堆栈深度，从而崩溃。