我正在尝试number of inversions使用merge sort.
合并步骤自然适用于反转的想法：ith元素大于jth元素。
def merge_and_count(x, y, result, count):
i, j = 0, 0
while i < len(x) and j < len(y):
if x[i] > y[j]:
result.append(y[j])
j += 1
count += 1
else:
result.append(x[i])
i += 1
result += x[i:]
result += y[j:]
return result, count
def sort_and_count(array):
if len(array) == 1:
return array, 0
count = 0
result = []
mid = len(array)//2
x = array[:mid]
y = array[mid:]
x, c1 = sort_and_count(x)
y, c2 = sort_and_count(y)
result, c3 = merge_and_count(x, y, result, count)
return result, (c1+c2+c3)
def main():
array = [1,3,5,2,4,6]
result, count = sort_and_count(array)
print("there are", count, "split inversion")
print(result)
然而，这是打印2时我的答案应该是3
您的merge_and_count函数中存在错误。它应该是：
if x[i] > y[j]:
result.append(y[j])
j += 1
count += len(x) - i # It's not +1 here
当您将下一个元素 from 附加y到结果时，它会与x尚未添加的所有元素形成反转。正是有len(x) - i这样的元素。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句