合并在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。