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

Question

我正在Python中研究合并排序。在

我检查了merge函数。阵列合并得很好。在

但是在mergeSort函数中出现了一个错误：--

RuntimeError: maximum recursion depth exceeded.

RuntimeError Traceback (most recent call last) in () 63 print(arr[i]), 64 ---> 65 mergeSort(arr,0,n-1) 66 print(" ") 67 print("Sorted Array is")

in mergeSort(arr, l, r) 53 m = l+(r-1)/2 54 mergeSort(arr,l,m) ---> 55 mergeSort(arr,m+1,r) 56 merge(arr,l,m,r) 57

可能的原因是什么？在

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

这是因为当您调用mergesort函数时，传递的是list的l=0和r=lenght。 不管你怎么计算，在任何情况下，你的l都会小于r

 m = l+(r-1)/2

Answer 2

在mergeSort中计算m的方法是错误的（您需要将整个表达式平分，而不仅仅是{}）。更改为：

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

当你计算错误时，你的方法不断地递归地调用自己，直到超过了最大方法堆栈深度，从而崩溃。在

Answer 3

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

楼层分割运算符（//）与普通除法运算符（/）

现在我们来谈谈为什么会出现递归错误，这里是答案

• 当你做手术的时候

m = (l+r)/2

除法运算将得到分数部分，即m将被视为浮动变量
所以m永远不会是0而是任何浮点数，比如说0.123或者2.122或者1.0025

因为浮点as m永远不会0，if条件if l<r:将始终为真，mergeSort（）函数进入无限循环，这就是为什么会出现运行时递归错误

You want m as integer and not float so instead of m=(l+r)/2

Write m=(l+r)//2 the floor division operator(//) will give you integer value and your mergeSort() function will not go under Infinite Loop

您的代码这次执行时不会出现任何错误，只需做一个更改m=（l+r）//2

但是您的merge（）函数algo不好，它不提供排序数组，数据也会丢失，并打印其他内容