5

我正在尝试使用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])
4

3 回答 3

3

修改您的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
于 2013-01-13T17:37:33.173 回答
2

您的代码中有一些问题：

  • 不要int()的结果len() / 2。如果您使用的是 Python3，我会直接使用带//运算符的整数除法。
  • 第一行的比较mergesort()是错误的。首先，不要is用于比较是否相等。is运算符仅用于标识。如果您有两个具有相同值的不同整数，则它们相等但不相同。对于小整数，我相信至少有一些 Python 方言会保留该值，因此您的比较有效，但您所依赖的东西并不能保证。尽管如此，使用==也不起作用，因为您忘记了空列表的情况。
  • 我猜您的实际问题（“奇怪的返回值”）是由于您返回两个值（作为元组）以一个名称存储的事实引起的，然后您将其作为参数传递给递归merge()调用。
于 2013-01-13T17:34:25.013 回答
0

由于在您的代码中合并返回一对，因此合并排序也必须返回一对。启用要在列表中获取总拆分反转，您必须添加左半部分、右半部分并合并拆分反转。

这是我在您的代码中所做的修改。

def mergesort(lst):
    '''Recursively divides list in halves to be sorted'''
    if len(lst) == 1:
        return lst, 0
    middle = len(lst)/2
    left, s1 = mergesort(lst[:middle])[0]  # Ignore intermediate splits
    right, s2 = mergesort(lst[middle:])[0]  # Ignore intermediate splits
    sortedlist, s3 = merge(left, right)
    return sortedlist, (s1+s2+s3)`
于 2013-07-10T04:34:46.510 回答