使用分而治之發現數列的反轉

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附加列表本身，這可能會導致您的問題。