>我已经完成了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 是交换次数。
下面是一个稍微修改过的代码版本,看起来可以工作:
def mergesortInv(list, mergeInv):
if len(list) < 2:
return list, 0
else:
middle = len(list) // 2
left, lc = mergesortInv(list[:middle], mergeInv) #definim les dues meitats
right, rc = mergesortInv(list[middle:], mergeInv)
merge, mc = mergeInv(left, right)
return merge, lc + rc + mc
def mergeInvRec(left, right):
if len(left) < 1:
return right, 0
if len(right) < 1:
return left, 0
if left[0] <= right[0]:
res, cnt = mergeInvRec(left[1:], right)
return [left[0]] + res, cnt
else:
res, cnt = mergeInvRec(left, right[1:])
return [right[0]] + res, len(left) + cnt
def mergeInvFlat(left, right):
res, cnt = [], 0
il, ir = 0, 0
nl, nr = len(left), len(right)
while il < nl and ir < nr:
if left[il] <= right[ir]:
res.append(left[il])
il += 1
else:
res.append(right[ir])
ir += 1
cnt += nl - il
res.extend(left[il:])
res.extend(right[ir:])
return res, cnt
这主要是记账的问题。计算每个步骤的交换次数并添加它们。在最后一个分支中,right
的第一个元素一直超过left
的每个元素,这就是为什么我们在那里计算len(left)
交换的原因。
编辑:正如@PM2Ring指出的那样,mergeInv
中的递归有点鲁莽,并且将超过Python对中等大小列表的最大递归深度。我添加了一个非递归版本。您可以通过将它们的名称作为第二个参数传递给 main 函数,在递归和非递归版本之间切换。
测试这个,但这只是为了让您了解我在对您的问题的评论中提出的建议。
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)
def mergeInv(left, right):
""" return a tuple of total swaps and the merged list """
if len(left) < 1:
return (0, right)
if len(right) < 1:
return (0, left)
if left[0] <= right[0]:
swaps, lst = mergeInv(left[1:],right)
return (swaps, [left[0]] + [lst])
else:
swaps, lst = mergeInv(left,right[1:])
return (swaps + 1, [right[0]] + [lst])
用法
swaps, lst = mergesortInv(mylist)