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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了合并排序以计算Python中的拆分反转，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1607字，纯文字阅读大概需要3分钟。

内容图文

我试图使用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])

解决方法:

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

内容总结

以上是互联网集市为您收集整理的合并排序以计算Python中的拆分反转全部内容，希望文章能够帮你解决合并排序以计算Python中的拆分反转所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端