本文介绍了计数反演使用合并排序的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我已经在Python做了一个合并排序程序,它是完全运行,但我已经修改了它算参与反转的数目,现在是给我的错误:

I have made a merge sort program in Python and it is running perfectly but I have modified it to count the number of inversions involved and now it is giving me an error :

下面是我的code:

def merge_list(left,right,c):
    result=[]
    i,j=0,0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            print "Left result",result
            i=i+1
        elif left[i] > right[j]:
            result.append(right[j])
            print "Right result",result
            j=j+1
        if right[j] < left[i]  and i<j:
            c=c+1
    result=result+left[i:]
    result=result+right[j:]
    print "Inversions: ",c
    return result,c


def sort_and_count(lis,count):

    if len(lis)<2:
        return lis
    middle=len(lis) / 2
    left,c1=sort_and_count(lis[:middle],count)
    print "left",left
    right,c2=sort_and_count(lis[middle:],count)
    print "right",right
    m,c=merge_list(left,right,count)
    c=c+c1+c2
    return m,c


if __name__=="__main__":

    print "Enter 6 elements: "
    i=0;lis=[];merge_lis=[];inv=0
    while i<=5:
        x=int(raw_input())
        lis.append(x)
        i=i+1
    count=0
    merge_lis,inv=sort_and_count(lis,count)
    print "Sorted list is: ",merge_lis,inv

和我回溯:

Traceback (most recent call last):
  File "Sort_and_count.py", line 53, in <module>
    merge_lis,inv=sort_and_count(lis,count)
  File "Sort_and_count.py", line 31, in sort_and_count
    left,c1=sort_and_count(lis[:middle],count)
  File "Sort_and_count.py", line 31, in sort_and_count
    left,c1=sort_and_count(lis[:middle],count)
ValueError: need more than 1 value to unpack

我要去哪里错了这种方法?

Where am I going wrong with this approach?

推荐答案

这行:

return lis

这是一个问题,因为你期待 sort_and_count 返回包含两个值的元组,所以当它仅返回一个值,你必须在元组拆包的问题如系留,C1 = sort_and_count(LIS [:中],计数)。此行应返回两个值,这样的方法的最后一行:

This is a problem, because you are expecting sort_and_count to return a tuple containing two values, so when it returns only one value you have a problem with the tuple unpacking in lines like left,c1=sort_and_count(lis[:middle],count). This line should return two values, like the last line of that method:

return m,c

这篇关于计数反演使用合并排序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-20 12:31