我已经完成了MergeSort算法,但我不知道如何计算交换。在
我的代码是:
def mergesortInv(list):
if len(list) < 2:
return list
else:
middle = len(list) // 2
left = mergesortInv(list[:middle]) #definim les dues meitats
right = mergesortInv(list[middle:])
swaps=???
return mergeInv(left, right,swaps)
def mergeInv(left, right,swaps):
if len(left) < 1:
return right
if len(right) < 1:
return left
if left[0] <= right[0]:
return [left[0]] + mergeInv(left[1:],right,swaps)
else:
return [right[0]] + mergeInv(left,right[1:],swaps)
该算法的输出将是已排序的列表(该部分的算法是有效的),交换的数量:mergesortInv(list) == ([1, 2, 3, 4, 5, 7, 8], 6)
6是交换的数量。在
下面是一个稍微修改过的代码版本,它似乎可以工作:
主要是记账的问题。计算每个步骤中交换的数量并将其相加。在最后一个分支中,
right
的第一个元素一路经过left
的每个元素,这就是我们在那里统计len(left)
交换的原因。在编辑:As@PM2Ring指出,
mergeInv
中的递归有点鲁莽,将超过Python对中等大小列表的最大递归深度。 我添加了一个非递归版本。通过将递归和非递归版本的名称作为第二个参数传递给main函数,可以在递归和非递归版本之间进行切换。在我没有对此进行测试,但这只是为了让您了解我在对您的问题的评论中提出的建议。在
使用情况
^{pr2}$相关问题 更多 >
编程相关推荐