我正在Python中研究合并排序。
我已经检查merge功能。数组合并正常。
但是在mergeSort函数中出现了错误：---
运行时错误：超出最大递归深度。
运行时错误回溯(最近一次调用( 最后( 在 (( 中 63 打印(到达[i](， 64 ---> 65 合并排序(arr，0，n-1( 66 打印(" "( 67 打印("排序数组是"(
in mergeSort(arr， l， r( 53 m = L+(R-1(/2 54 mergeSort(arr，l，m( ---> 55 mergeSort(arr，m+1，r( 56 合并(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])
mergeSort计算m的方式是错误的(你需要将整个表达式分成两半，而不仅仅是(r-1)(。将其更改为：
m = (l+(r-1))/2
当您计算错误时，您的方法会一遍又一遍地递归调用自己，直到超过最大方法堆栈深度并因此崩溃。
- 你犯了基本的错误。Python是动态类型语言
- 在讨论为什么你得到运行时递归错误之前，你需要做一个更改.
而不是m = l+(r-1)/2写m = (l+r)/2
因为当你在那个时候调用mergeSort(arr,0,n-1)时n-1是最后一个索引值，这就是为什么不需要r-1m = l+(r-1)/2
地板分割运算符(//( VS 普通除法运算符(/(
现在来到重点，为什么你会得到递归错误这里是答案
- 当您执行以下操作时
m = (L+R(/2
除法运算将给出小数部分，即m将被视为浮动变量
所以m永远不会是0它将是任何浮点数，比如0.123或2.122或1.0025
由于浮点m永远不会为0，if条件if l<r:将始终为真，并且mergeSort((函数进入无限循环，这就是您得到运行时递归错误的原因
您希望m作为整数而不是浮点数，而不是 m=(l+r(/2
写m=(l+r(//2 地板除法运算符 (//( 会给你整数值，你的mergeSort((函数不会进入无限循环
这次您的代码将执行，没有任何错误，只需进行一次更改m=(l+r(//2
但是但是但是但是你的 merge(( 函数算法不好，它没有给出排序数组，数据也会丢失，其他东西会被打印出来
这是因为当你调用mergesort函数时，你传递的是l = 0和r=列表的长度。 无论你在每种情况下的计算结果如何，你 l 都将小于 r。
m = l+(r-1)/2