使用分而治之发现数列的反转

Question

我遇到了a post in SO其中算法是用python代码实现的。这是在this article中伪代码的直接实现。

然而，在伪代码中，存在这样的情况计数是通过残留在数组元素“a'.In上述Python代码的数目增加一条线，它被给定为

count += len(a) - i 

不能我们做同样的

count += len(a[i:]) 

此外，而不是

c += a[i:] + b[j:] 

我写的，

c.append(a[i:]) 
c.append(b[j:]) 

总共我的版本是这样的

def merge(left,right): 
    i=0 
    j=0 
    count=0 
    c=[] 
    while i<len(left) and j<len(right): 
     c.append(min(left[i],right[j])) 
     if right[j]< left[i]: 
      count+=len(left[i:]) 
      j+=1 
     else: 
      i+=1 
    c.append(left[i:]) 
    c.append(right[j:]) 
    return count,c 


def dnc(input): 
    if len(input)==1: 
     return 0,input 
    mid=len(input)/2 
    left=input[:mid] 
    right=input[mid:] 
    l,left=dnc(left) 
    r,right=dnc(right) 
    m,result=merge(left,right) 
    count=l+r+m 
    return count,result 

唉！当我计算这个排序的阵列上，我得到的3而不是0

if __name__=='__main__': 
    input =[1,2,3,4,5] 
    ct,res=dnc(input) 
    print ct 

我做了什么错误？有人能帮我找出答案吗？

Answer 1

这里就是我可以建议：

• 不要做count += len(a[i:])。它比原来慢，并且不必要地使逻辑复杂化。我会将len(a)缓存为len_a并在循环之外计算一次，因为a似乎未被修改。

• c += a[i:] + b[j:]与c.extend(a[i:])和c.extend(b[j:])相同。 extend将的内容附加到c，而append附加列表本身，这可能会导致您的问题。