合并排序以计算Python中的分割反转

Question

我正在尝试使用mergesort-我得到的-
计算列表中拆分反转的数量（也就是说，未排序列表的前半部分中的元素应该出现在列表的后半部分中的给定元素之后未排序的列表；例如[3 2 1
4]将包含分割反转（3，1），但不包含（3，2），因为3和2都在上半部。当我到达最终的打印语句时，我得到了我期望的答案-
在这种情况下为9-但是返回值都是不正确的，因为它通过递归返回分割值。我尝试了各种索引组合都无济于事。有什么帮助吗？（使用Python 2.7）

（据记录，这是Coursera的家庭作业问题，但我只是在学习乐趣-除了我以外，没有人对此评分。）

def mergesort(lst):
    '''Recursively divides list in halves to be sorted'''
    if len(lst) is 1:
        return lst
    middle = int(len(lst)/2)
    left  = mergesort(lst[:middle])
    right = mergesort(lst[middle:])
    sortedlist = merge(left, right)
    return sortedlist

def merge(left, right):
    '''Subroutine of mergesort to sort split lists.  Also returns number
    of split inversions (i.e., each occurence of a number from the sorted second
    half of the list appearing before a number from the sorted first half)'''
    i, j = 0, 0
    splits = 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            splits += len(left[i:])
    result += left[i:]
    result += right[j:]
    print result, splits
    return result, splits


print mergesort([7,2,6,4,5,1,3,8])

Answer 1

修改您的mergesort功能以忽略中间拆分。

def mergesort(lst):
    '''Recursively divides list in halves to be sorted'''
    if len(lst) == 1:
        return lst, 0
    middle = len(lst)/2
    left = mergesort(lst[:middle])[0]  # Ignore intermediate splits
    right = mergesort(lst[middle:])[0]  # Ignore intermediate splits
    sortedlist, splits = merge(left, right)
    return sortedlist, splits