Python遞歸合併排序不工作

我想實現一個遞歸合併排序算法，只有函數返回任何東西，但我很難得到它的工作。好像它正在分解列表並正確排序它們，但沒有將這些已排序的列表轉移到下一個遞歸調用中。Python遞歸合併排序不工作

def merge(list1, list2): 
    result = [] 
    i = 0 
    j = 0 
    k = 0 
    while i < len(list1) and j < len(list2): 
     if list1[i] < list2[j]: 
      result.append(list1[i]) 
      i+=1 
     else: 
      result.append(list2[j]) 
      j+=1     
     k+=1 
    while i < len(list1): 
     result.append(list1[i]) 
     i+=1 
     k+=1 
    while j < len(list2): 
     result.append(list2[j]) 
     j+=1 
     k+=1 
    print(result) 


def merge_sort(inplist): 
    if int(len(inplist)) >1: 
     mid = len(inplist)//2 
     left = inplist[0:mid] 
     right = inplist[mid:] 
     merge_sort(left) 
     merge_sort(right) 
     merge(left,right) 


test = [1,4,7,2,6,9,8,5,3,0] 
merge_sort(test) 
print(test)

來源

2015-07-03 Esteban D

索引列表創建一個新列表（left = inplist[0:mid]）。由於您似乎沒有將這些新列表（合併後）重新分配給inplist，因此inplist將不會發生任何事情。

事實上，merge()合併兩個名單，但隨後扔掉的結果：在創建result內merge()，但你不要用它做任何事情，所以它會在函數退出後丟棄。

我想你需要從merge()返回result並將它分配給inplist; （未經測試）：

inplist[:] = merge(left, right)

來源

2015-07-03 04:17:22 Evert

merge_sort是一個遞歸函數，是否會正確地從第二或第三級遞歸值中繼承？ –

@AnandSKumar我想這取決於你如何設置它，但我認爲這應該工作，是的。主要是因爲你將最終結果再次分配給原始列表;任何中間列表可以是對原始列表（的部分）的複製或引用，但是在那一點上不再重要。當然，從內存使用的意義上講它確實很重要;在這種情況下，你總是需要傳遞完整的列表，加上相關的開始和結束索引（很像C中的一樣）。 – Evert

Python遞歸合併排序不工作

回答

相關問題