使用Python实现归并排序以计算拆分逆序对

Question

使用Python实现归并排序以计算拆分逆序对

4

我正在尝试使用归并排序来计算列表中的拆分逆序对数量（即未排序列表的前半部分中的元素应在未排序列表的后半部分中的给定元素之后出现；例如，[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])

- thumbtackthief

如果len(lst)等于1？为什么不使用 == 运算符？ - user2665694

中间 = int(len(lst)/2)？为什么要在这里使用int()函数？ - user2665694

那么，这是一个堆栈式的问题。我知道这些东西是错误的，虽然与手头的问题无关 - 我是否应该回去编辑我的原始代码，还是那会让未来读者更加困惑？ - thumbtackthief

1

@thumbtackthief，这门课程真是太难了，我现在正在苦苦挣扎。我甚至无法想象它会如此困难。而且这只是第一周。 - micgeronimo

3个回答

2

你的代码中有几个问题：

不要对len() / 2的结果使用int()。如果你在使用Python3，应该直接使用整数除法，即使用//运算符。
mergesort()函数第一行的比较是错误的。首先，不要使用is运算符进行相等比较。is运算符仅用于身份比较。如果你有两个不同的整数具有相同的值，它们是相等但不是相同的。对于小整数，我相信至少有一些Python方言将这个值内部化（intern），因此你的比较有效，但你依赖于不能保证的东西。而使用==也不行，因为你忘记了空列表的情况。
我猜你实际的问题（“奇怪的返回值”）是由于你返回两个值，你把它们作为一个名字下的元组存储并作为参数传递给递归调用的merge()函数。

- Ulrich Eckhardt

a) 我认为int()是不必要的。它在我的阅读材料中被包含，所以我想可能有一些目的我没有看到。b) 我正在准备白板面试。我有一个习惯，就是当我想要输入==时，会误打成=（我在第一次测试中就发现了），但我担心我会犯这个错误。我刚刚发现了'is'——我想我还不清楚它与==有什么不同。c) 这确实是我的问题；我尝试将其作为两个变量返回——我认为这是显而易见的解决方案——但这并没有帮助。 - thumbtackthief

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)`

- Jofel Bayron

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tim · Accepted Answer

修改您的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