1

我已经实现了合并排序，除了排序之外，我还希望它计算原始数组中的反转数。

下面是我实现它的尝试，由于某种原因，它不能正确计算反转的数量。

例如，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
4

2 回答 2

2

主要问题不包括排序左侧和右侧的计数。

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
于 2017-02-19T18:59:04.073 回答
0

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

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

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

def count_inversions(data):
    count, result = mergeSort(data)
    return count

test_cases = [
    (3, [1,3,5,2,4,6]),
    (590, [37, 7, 2, 14, 35, 47, 10, 24, 44, 17, 34, 11, 16, 48, 1, 39, 6, 33, 43, 26, 40, 4, 28, 5, 38, 41, 42, 12, 13, 21, 29, 18, 3, 19, 0, 32, 46, 27, 31, 25, 15, 36, 20, 8, 9, 49, 22, 23, 30, 45]),
    (2372, [4, 80, 70, 23, 9, 60, 68, 27, 66, 78, 12, 40, 52, 53, 44, 8, 49, 28, 18, 46, 21, 39, 51, 7, 87, 99, 69, 62, 84, 6, 79, 67, 14, 98, 83, 0, 96, 5, 82, 10, 26, 48, 3, 2, 15, 92, 11, 55, 63, 97, 43, 45, 81, 42, 95, 20, 25, 74, 24, 72, 91, 35, 86, 19, 75, 58, 71, 47, 76, 59, 64, 93, 17, 50, 56, 94, 90, 89, 32, 37, 34, 65, 1, 73, 41, 36, 57, 77, 30, 22, 13, 29, 38, 16, 88, 61, 31, 85, 33, 54]),
]

def validate():
    for expected, data in test_cases:
        answer = count_inversions(data)
        if answer != expected:
            print "FAILED VALIDATION -- actual:", answer, "expected:", expected, "data:", data

validate()
于 2017-02-19T18:55:46.993 回答