Mergesort遞歸錯誤

Question

我編碼這合併代碼在python.The函數合併工作正常，當我單獨調用它，它排序兩個不同的排序lists.But當我在真正的合併排序遞歸問題中使用它時，它不做它的預期幹活。我上傳我的代碼，請幫助我在這個問題

def merge(list,p,q,r): 

    list1=[] 
    list2=[] 
    list3=[] 
    i=0 
    j=0 
    for a in list[:q+1]: 
     list1.append(a) 
    list1.append(99999999999) 

    for b in list[q+1:]: 
     list2.append(b) 
    list2.append(9999999999999999999999999) 
    for k in range(len(list)): 
     if list1[i]<list2[j]: 
      list3.insert(k,list1[i]) 
      i=i+1 
     else: 
      list3.insert(k,list2[j]) 
      j=j+1 
     return list3 




def mergesort(list,p,r): 

    if p<r: 

     q=(p+r)/2 
     mergesort(list,p,q) 
     mergesort(list,q+1,r) 
     merge(list,p,q,r) 


list=[1,5,7,8,2,4,6,9] 

mergesort(list,0,7) 

print list 

有沒有intendation錯誤

輸出爲：

[1, 5, 7, 8, 2, 4, 6, 9] 

其打印一樣的列表 不選它

Answer 1

你是不是對矯正列表中選擇功能「merge」

裏面你要麼需要修改list或return新list，你正在做既不

您可以從合併功能 返回項目list3和修改歸併爲：

def mergesort(list,p,r): 
    if p<r: 
     q=(p+r)/2 
     mergesort(list,p,q) 
     mergesort(list,q+1,r) 
     list =merge(list,p,q,r) 

嗨瘋狂Ë它的工作： 使用

def merge(list,p,q,r): 

    list1=[] 
    list2=[] 
    list3=[] 
    i=0 
    j=0 
    for a in list[:q+1]: 
     list1.append(a) 
    list1.append(99999999999) 

    for b in list[q+1:]: 
     list2.append(b) 
    list2.append(9999999999999999999999999) 
    for k in range(len(list)): 
     if list1[i]<list2[j]: 
      list3.insert(k,list1[i]) 
      i=i+1 
     else: 
      list3.insert(k,list2[j]) 
      j=j+1 
    return list3 




def mergesort(list,p,r): 

    if p<r: 

     q=(p+r)/2 
     mergesort(list,p,q) 
     mergesort(list,q+1,r) 
     list = merge(list,p,q,r) 
     return list 

list=[1,5,7,8,2,4,6,9] 

list = mergesort(list,0,7) 

print list