如何使用合并排序计算反转?

Question

我正在尝试使用 def count_inversion 计算反转的总次数

def count_inversion(alist):
count = 0
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
a=count_inversion(lefthalf)
b=count_inversion(righthalf)
i=0
j=0
k=0
track = 0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
count+=len(righthalf[i:])
k=k+1
while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1

while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
return count
def main():
alist = [10,9,8,7,6,5,4,3,2,1]
inversion = count_inversion(alist)
print(alist)
print(inversion)    
main()

我确实得到了一个排序列表[1,2,3,4,5,6,7,8,9,10]，但对于反转计数，它显示它是 25 而不是 45.我想我可能会在我的代码中犯一些错误，但我不知道如何解决它......如果有人能帮助我，将不胜感激...

Answer 1

# store inversion count 
count+=count_inversion(lefthalf)
count+=count_inversion(righthalf)
# updated line > Instead of righthalf count length of lefthalf
count+=len(lefthalf[i:])

更新代码中的这 2 行

Answer 2

这是我在类函数中的实现。这也算作反转。您可以取消注释语句以查看跟踪反转的替代方法。

class MergeSort(object):
'''
Instantiates an array into the object from which the method 'merge_sort' can be called.
Returns number of inversions and sorted array.
>>>x = MergeSort([1,6,5,2,10,8,7,4,3,9])
>>>x.merge_sort()
(20, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
'''
def __init__(self, array):
self.array = array
def merge_sort(self):
count = 0
#count_ = []
if len(self.array) > 1:
m = len(self.array)//2
left = self.array[:m]
right = self.array[m:]
leftsorter = MergeSort(left)
leftsorter = leftsorter.merge_sort()
rightsorter = MergeSort(right)
rightsorter = rightsorter.merge_sort()
# Two different ways to track inversions
# numeric counter, better way
count += leftsorter[0]
count += rightsorter[0]
# list counter
#count_.append(leftsorter[0])
#count_.append(rightsorter[0])
i = 0
j = 0
k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
self.array[k] = left[i]
i += 1
else:
self.array[k] = right[j]
j += 1
count += len(left[i:])
#count_.append(len(left[i:]))
k += 1
while i < len(left):
self.array[k] = left[i]
i += 1
k += 1
while j < len(right):
self.array[k] = right[j]
j += 1
k += 1
return count, self.array, #sum(count_)

这样运行。

array = [1,6,5,2,10,8,7,4,3,9]
x = MergeSort(array)
x.merge_sort()
Out[ ]:
(20, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

Answer 3

你不能使用这个示例代码吗？ https://www.geeksforgeeks.org/counting-inversions/