合併排序沒有正確發生 - Python

Question

排序沒有正確發生。有人可以幫助用這種方法分類。也請讓我知道我要去哪裏錯了。我是Python的新手，所以我自己也是這樣做的。我使用通常的方法，就像我們用C或其他語言做的那樣。

base =[5,4,3,2,1] 

def splitarray (low, high): 
    if low < high: 
     mid = (high+low)/2 

     splitarray (low, mid) 
     splitarray (mid+1,high) 
     merge(low,mid,high) 

    else: 
     return 

def merge(low,mid,high): 
    print("merge " +str(low) + " - " +str(mid)+" - "+ str(high)) 
    result = [0]*len(base) 
    k = 0 
    i=low 
    j=mid+1 
    l=0 


    while i <= mid and j <= high: 
     if (base[i] < base[j]): 

      result[k]= base[i] 
      k+=1 
      i += 1 

     if (base[i] > base[j]) : 


      result[k]= base[j] 

      j += 1 
      k += 1 





    while i <= mid: 
     result[k]= base[i] 
     k += 1 
     i += 1 
    while j <= high: 
     result[k]= base[j] 
     #count = count + mid - i 
     j += 1 
     k += 1 

    print result 

    l = low 
    k= 0 
    while l <= high: 
     base[l] = result[l] 
     l += 1 


    print base 
splitarray(0,len(base)-1) 

Answer 1

與您當前的（更新）代碼的問題似乎是與最後一個循環：

l = low 
k= 0 
while l <= high: 
    base[l] = result[l] 
    l += 1 

在這裏，我們從results列表中的值複製到base列表。但是，結果全部在results開頭，與base的座標不同。你似乎有差不多是因爲你將k設置爲零而得到了正確的結果，但是你不會在循環中使用k。

嘗試：

l = low 
k= 0 
while l <= high: 
    base[l] = result[k] # read the result from index k, not l 
    l += 1 
    k += 1 # increment k as well 

這應該工作打算。請注意，雖然這將正確排序，但這不是一種用Python排序的優雅方式。首先，您只能對一個全局變量base進行排序，而不是任何列表（將列表作爲參數傳遞會更好）。然而，由於這看起來像你寫的主要是爲了學習體驗，我會給你留下進一步的改進。

Answer 2

視覺上的算法操作方法是：

因此實現合併排序的最明顯的方法是返回一個新的列表中爲每個合併。也許這可以優化，看起來像你試圖做的，這是在一個頂級的操作result。但是如果你這樣做，你不能在每一級合併時追加到result。因爲在遞歸的最底層，你將添加四個元素，然後在中間級別添加四個元素，然後在頂層添加四個元素。太多了。如果你這樣做，你應該有一個固定的result大小，並在整個執行過程中對其索引進行操作。

第二個錯誤是您正在閱讀每個合併的未修改base。每個合併步驟的先決條件是合併的兩個列表已經排序。如果您以顯而易見的方式實現算法，則可以使用來自更深層合併的返回值。如果您正在使用頂級result以某種優化方式實現算法，那麼您應該從result而不是base讀取。