合并排序中的反转次数 python

Question

我正在尝试计算合并排序算法中的倒置次数。除了为条件添加一个计数器以在右侧的值小于左侧的值时翻转值外，我没有做太多修改。我正在使用的代码如下，它甚至在 pythontutor.com 上打印出正确答案，但也会产生错误。我无法理解的是错误的来源。这里有人能解释一下我没有看到什么吗？下面是我的代码以及错误：

def merge(left,right):
    result=[]
    i,j=0,0
    count=0
    while (i<len(left)) and (j<len(right)):
      if left[i]<right[j]:
          result.append(left[i])
          count+=1
          i+=1
      else:
          result.append(right[j])
          j+=1

    while (i<len(left)):
      result.append(left[i])
      i+=1

    while (j<len(right)):
      result.append(right[j])
      j+=1
   # print(count)
 return result,count

def merge_sort(list):
    if len(list)<2:
        return list
    else:
        middle=len(list)//2
        left=merge_sort(list[:middle])
        right=merge_sort(list[middle:])
        # return merge(left,right)
        result,count=merge(left,right)
        print(result,count)

merge_sort([2,3,9,2,9])

我得到的错误是：

TypeError: object of type 'NoneType' has no len()

Answer 1

您的问题出在 merge_sort 函数的 else 块中 - 您从未 return 您的列表，因此 Python 隐式 returns None。你想要这样的东西：

left,   left_count  = merge_sort(list[:middle])
right,  right_count = merge_sort(list[middle:])
result, merge_count = merge(left, right)

count = left_count + right_count + merge_count
return result, count

旁白：您不应该使用内置类型（例如“list”）作为变量名，因为它们掩盖了实际类型。

合并排序中的反转次数 python

Number of Inversions in Merge Sort python

python

algorithm

mergesort

divide-and-conquer