Python递归合并排序不工作

Question

我想实现一个递归合并排序算法，只有函数返回任何东西，但我很难得到它的工作。好像它正在分解列表并正确排序它们，但没有将这些已排序的列表转移到下一个递归调用中。

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) 

Answer 1

索引列表创建一个新列表（left = inplist[0:mid]）。由于您似乎没有将这些新列表（合并后）重新分配给inplist，因此inplist将不会发生任何事情。

事实上，merge()合并两个名单，但随后扔掉的结果：在创建result内merge()，但你不要用它做任何事情，所以它会在函数退出后丢弃。

我想你需要从merge()返回result并将它分配给inplist; （未经测试）：

inplist[:] = merge(left, right)