在递归期间难以维护变量的值

Question

我正在尝试使用分而治之法计算数组中的倒置数 methodology.However，我无法保持倒置总数。程序完成后 returns 倒置次数在最后一步而不是之前完成的所有反转的总和。

def mergesort(A):
 if len(A) <2:
    return A
 mid = len(A)//2
 lefthalf = A[:mid]
 righthalf = A[mid:]
 mergesort(lefthalf)
 mergesort(righthalf)
 Total= merge(lefthalf,righthalf,A)
 return Total

def merge(left,right,A):
 Total = 0
 i,j,k = 0,0,0
 while i < len(left) and j < len(right):
     if left[i] <= right[j]:
         A[k] = left[i]
         i+=1
         k+=1
     else:
         A[k] = right[j]
         j+=1
         k+=1
         Total+= len(left[i:]) 
 while i < len(left):
      A[k] = left[i]
      i+=1
      k+=1
 while j < len(right):
      A[k] = right[j]
      j+=1
      k+=1  
 return Total

打印（合并排序（[1,5,3,2,4]））

如何保持总计？请建议对代码进行必要的更改并附上解释。谢谢

Answer 1

为了完整起见，这里有一个答案，所以这个问题不会留在未回答的部分。

您的总数不仅需要跟踪当前堆栈帧中的反转次数，还需要跟踪未来递归调用的堆栈帧中的反转次数。为此，您需要将递归调用的 return 值添加到 Total，或者将 Total 声明为将在每个递归调用之间共享的全局变量，而不是像现在那样保留局部变量。

在递归期间难以维护变量的值

Difficulty mantaining value of a variable during Recursion

recursion

divide-and-conquer

python-3.x