python - 合并排序以计算 Python 中的拆分反转

Question

我正在尝试使用合并排序——我得到了——来计算列表中拆分反转的次数(也就是说，未排序列表的前半部分中的元素应该出现在第二部分中的给定元素之后未排序列表的一半；例如 [3 2 1 4] 将包含拆分反转 (3, 1)，但不包含 (3, 2)，因为 3 和 2 都在前半部分)。当我到达最终的 print 语句时，我得到了我期望的答案——在本例中为 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