合并排序python中的反转数

哈西卜·汗

我正在尝试计算合并排序算法中的反转次数。我没有做很多修改，除了为条件添加一个计数器以在右侧的值小于左侧的值时翻转值。我正在使用的代码如下，它甚至在 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()

狄龙戴维斯

你的问题出在else你的merge_sort函数块中——你永远不会返回你的列表，所以 Python 隐式返回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

旁白：您不应该使用内置类型（例如“列表”）作为变量名，因为它们会影响实际类型。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。