歸併，問題與遞歸基本情況和訂購

Question

我在歸併算法的Python作了如下實施：

def mergeSort(listNumbers,ini,end): 
    if ini==end: 
     return listNumbers 
    else: 
     mid=(ini+end)/2 
     mergeSort(listNumbers,ini,mid) 
     mergeSort(listNumbers,mid+1,end) 
     merge(listNumbers,ini,mid,end) 

def merge(listNumbersT,ini,mid,end): 
    b=[] 
    ind1=ini 
    ind2=mid+1 
    while ind1<=mid and ind2<=end: 
     if listNumbersT[ind1]<listNumbersT[ind2]: 
      b.append(listNumbersT[ind1]) 
      ind1=ind1+1 
     else: 
      b.append(listNumbersT[ind2]) 
      ind2=ind2+1 
    while ind1<=mid: 
     b.append(listNumbersT[ind1]) 
     ind1=ind1+1 
    while ind2<=end: 
     b.append(listNumbersT[ind2]) 
     ind2=ind2+1 
    listNumbersT=b 
    print listNumbersT 

def main(): 
    l=[4,1,8,2,5,9,10] 
    print mergeSort(l,0,len(l)-1) 

if __name__=="__main__": 
    main() 

我不知道如何解決我的遞歸調用歸併，當時的基本情況我運行程序打印無;而我唯一的方式來打印最後的結果是增加：

打印listNumbersT

在合併功能

，我怎麼能解決這個問題？它似乎也沒有排列我列表中的最後一個元素。

任何幫助？

感謝

Answer 1

我得到這個通過使您的排序就地工作。在一些地方，你是返回列表，其他地方不是很多。

訂正mergeSort函數是這樣的：

def mergeSort(listNumbers,ini,end): 
    if ini < end: 
     mid=(ini+end)/2 
     mergeSort(listNumbers,ini,mid) 
     mergeSort(listNumbers,mid+1,end) 
     merge(listNumbers,ini,mid,end) 

這意味着鹼的情況是當ini >= end，listNumbers保持不變。

在merge函數結束時，我代替你的listNumbersT = b有：

for i,value in enumerate(b): 
     listNumbersT[ini + i] = value 

其副本b回到原來listNumbersT的元素。同樣，這會使原始列表中的「原地」更改，因此不需要返回任何內容。

這才叫那些main：

def main(): 
    l=[4,1,8,2,5,9,10] 
    mergeSort(l,0,len(l)-1) # sort l in-place 
    print l     # [1, 2, 4, 5, 8, 9, 10] 

---

一個小調整 - 通過改變mergeSort功能的開始

def mergeSort(listNumbers,ini=0,end=-1): 
    if end < 0: 
     end += len(listNumbers) 

在main調用簡直就成了：

mergeSort(l) 

這使用戶稍微容易一些。

Answer 2

在不改變你的代碼太多，

在你的函數merge行listNumbersT=b重新分配變量listNumbersT因爲這個原因，你失去你有沒有價值，破壞你的遞歸。

要解決該問題，請在函數merge中用以下循環替換listNumbersT=b。

for i,number in enumerate(b): 
    listNumbersT[ini + i] = number 

要獲得正確的回報，你必須在你的歸併函數的最後回報，如

def mergeSort(listNumbers,ini,end): 
    if ini==end: 
     return listNumbers 
    else: 
     mid=(ini+end)/2 
     mergeSort(listNumbers,ini,mid) 
     mergeSort(listNumbers,mid+1,end) 
     merge(listNumbers,ini,mid,end) 

    return listNumbers 

然而，l會在原地重新排序，所以你真的不需要在mergeSort結束時返回。

乾杯