在 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)

如果我没理解错的话，该函数会一遍又一遍地划分列表的左半部分，创建越来越小的子列表，直到它们只有一项那么长，然后继续移动到右半部分。那是对的吗？例如：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]，然后再向后工作。下一步是将 [3, 4] 分解为 [3] 和 [4]，然后返回 [5, 6, 7, 8] 并重复所有相同的步骤。对吗？

我的另一个问题是，为了重新组合所有的小子列表，不应该将 i 和 j 重置为 0 吗？例如：对于 [1] 和 [2] 变为 [1, 2] i 和 j 变为 1，但是它们不能指向 [3] 和 [4] 变为 [3, 4] 因为它们都在索引 0。我在这里缺少什么？

Answer 1

不要考虑整个过程。递归思考。谁在乎哪个列表先被分解？您只需要知道：

基本情况是否正确？在这种情况下，您是否可以什么都不做对 1 个或更少元素的列表进行排序？答案是肯定的。
递归调用是否接近基本情况？在这种情况下，列表参数逐渐变小，最终长度为 0 或 1，是的。
最后但同样重要的是...假设递归调用执行它们应该执行的操作，函数的其余部分是否相应地运行？在这种情况下，如果您拆分 alist ，对每一半进行排序，然后像 3 个 while 循环一样将两半合并为 alist，它是否已排序？答案再次是肯定的。

对于您的另一个问题，一次调用中的 i、j 和 k 完全独立于其他调用中的那些。即使它们不是，它们也会在 while 循环开始之前被设置为 0。

在 Python3 中合并排序

Merge Sort in Python3

python

python-3.x

mergesort