合併在Python3中排序

Question

我有一些工作代碼，但我不太明白它爲什麼起作用。如果有人能夠引導我閱讀其中的一些內容，或者解釋我在我的假設中錯誤的地方，我會非常感激。

下面是代碼：

def mergeSort(alist): 
    print("Splitting ",alist) 
    if len(alist)>1: 
     mid = len(alist)//2 
     lefthalf = alist[:mid] 
     righthalf = alist[mid:] 

     mergeSort(lefthalf) 
     mergeSort(righthalf) 

     i=0 
     j=0 
     k=0 
     while i < len(lefthalf) and j < len(righthalf): 
      if lefthalf[i] < righthalf[j]: 
       alist[k]=lefthalf[i] 
       i=i+1 
      else: 
       alist[k]=righthalf[j] 
       j=j+1 
      k=k+1 

     while i < len(lefthalf): 
      alist[k]=lefthalf[i] 
      i=i+1 
      k=k+1 

     while j < len(righthalf): 
      alist[k]=righthalf[j] 
      j=j+1 
      k=k+1 
    print("Merging ",alist) 

alist = [54,26,93,17,77,31,44,55,20] 
mergeSort(alist) 
print(alist) 

如果我理解正確的話，該函數將遍地劃分列表的左半部分，創造越來越小的子列表，直到他們只有一個項目長，然後移動到右邊一半。那是對的嗎？ EX：list = [1,2,3,4,5,6,7,8]將被分解爲[1,2,3,4]和[5,6,7,8]，則函數將會中斷左半部分進入[1，2]和[3，4]，然後[1，2]進入[1]和[2]，然後再向後運動。下一步是在返回[5,6,7,8]之前將[3,4]分成[3]和[4]並重復所有相同的步驟。那是對的嗎？

我的另一個問題是，我不應該重置爲0以重新組合所有小的子列表嗎？ EX：[1]和[2]變成[1,2] i和j變成1，但是他們不能指向[3]和[4]變成[3,4]，因爲它們都是索引0.我在這裏錯過了什麼？

Answer 1

不要考慮整個程序。遞歸地思考。誰關心哪個列表首先被分解？所有你需要知道的是：

• 基本情況是否正確？在這種情況下，你可以通過什麼都不做什麼來排序1個或更少的元素的列表？答案是肯定的。
• 遞歸調用是否接近基本情況？在這種情況下，列表參數逐漸變小，最終長度爲0或1，所以是的。
• 最後但並非最不重要的......假定遞歸調用做他們應該做的事，函數的其餘部分是否相應地行爲？在這種情況下，如果拆分alist，則對每一半進行排序，並將兩個半部分合併到alist中，如3個while循環所示，是否對它進行排序？答案也是肯定的。

對於你的另一個問題，i，j和k一個電話是完全獨立於其他調用者的。即使它們不是，在while循環開始之前，它們被設置爲0。