合并中倒数的计数

Question

我实现了一个合并排序，除了排序之外，我还希望它计算原始数组中inversions的数目。在

下面是我实现它的尝试，因为某些原因，它没有正确计算反转的次数。在

例如，mergeSort([4, 3, 2, 1])应该返回(6, [1, 2, 3, 4])。在

def mergeSort(alist):
    count = 0  
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=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]
                count +=len(lefthalf[i:])
                j=j+1    
            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, alist

Answer 1

主要的问题是不包括对左右两侧进行排序的计数。在

def mergeSort(alist):
    count = 0
    leftcount = 0
    rightcount = 0
    blist = [] 
    if len(alist) > 1:
       mid = len(alist) // 2
       lefthalf = alist[:mid]
       righthalf = alist[mid:]
       leftcount, lefthalf = mergeSort(lefthalf)
       rightcount, righthalf = mergeSort(righthalf)

       i = 0
       j = 0

       while i < len(lefthalf) and j < len(righthalf):
         if lefthalf[i] < righthalf[j]:
             blist.append(lefthalf[i])
             i += 1
         else:
             blist.append(righthalf[j])
             j += 1
             count += len(lefthalf[i:])

       while i < len(lefthalf):
          blist.append(lefthalf[i])
          i += 1

       while j < len(righthalf):
          blist.append(righthalf[j])
          j += 1
    else:
        blist = alist[:]

    return count + leftcount + rightcount, blist

Answer 2

您的函数返回一个元组（inversion，sortedlist）。但是，您的内部递归调用完全忽略了这一点，因此您在顶层以下计数的任何反转都被简单地丢弃在一边而不进行计数。在

  lc, lefthalf = mergeSort(alist[:mid])
  rc, righthalf = mergeSort(alist[mid:])
  count = count + lc + rc

如果你和同学分享这个，你可以用这个：

^{pr2}$