时间戳

首页 > 解决方案 > 使用归并排序的反转次数

python - 使用归并排序的反转次数

问题描述

我编写了这段代码来使用 获取反转次数merge_sort，但我没有得到正确的输出。有人能告诉我为什么它给出错误的输出吗？

def merge(B,C):  # B,C are sorted
  D = list()
  count = 0
  # empty list to get the merged list
  while (B != []) and (C != []):  # breaks if any one of B or C becomes empty

    b = B[0]  # to get first element of B
    print("b",b)
    c = C[0]  # to get first element of C
    print("c",c)
    
    if b<=c:
      B.remove(b)  # if b<c remove b from B and add to D
      D.append(b)
    else:
      C.remove(c)  # if b>c remove c from C and add to D
      D.append(c)
      count += 1
      print("count_in_merge",count)

  # now if either one of B or C has become empty so while loop is exited
  # so we can add remaining elements of B and C as it is to D as they are
  # already sorted
  if B != []:                                       
    for i in B:
      D.append(i)
  
  if C != []:
     for i in C:
      D.append(i)

  return D, count 

def sort_and_num(A):
  if len(A) == 1:
    return A,0

  m = len(A) // 2
    
  B,count_b = sort_and_num(A[0:m])
  C,count_c = sort_and_num(A[m:])
    
  A_,count = merge(B,C)
  count += (count_b + count_c)
  
  return A_, count

当我运行时：

A = [ 9, 8 ,7, 3, 2, 1] 
A_,c = sort_and_num(A)
print(A_,c)

输出是：

[1, 2, 3, 7, 8, 9] 9

但输出应该是

[1, 2, 3, 7, 8, 9] 15

另一方面，如果我输入：

A = [3,1,2,4] 
A_, count = sort_and_num(A)
print(A_, count)

输出是：

[1,2,3,4 ] 3

哪个是对的。它哪里出错了？

标签： pythonalgorithmsortingmergesort

解决方案

在此代码片段中：

else:
    C.remove(c)  # if b>c remove c from C and add to D
    D.append(c)
    count += 1

您应该按列表count其余部分的长度进行更新B

    count += len(B)

因为从右侧移动一个元素可能会一次“纠正”许多反转。

另请注意，由于会立即从列表中删除元素，因此选择的实现相当无效。

推荐阅读