python递归函数中的合并排序代码

Question

我正在尝试理解下面的python合并排序代码。在

函数mergeSort没有返回任何值，也没有将排序后的列表存储到lefthalf变量中。那么在函数被调用后，变量lefthalf的值是如何改变的{对于eg是[26,54]}。在

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

        print("Before left call------>",lefthalf)
        mergeSort(lefthalf)
        print("after left call------>",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)

输出：

^{pr2}$

。。。 ... 以此类推，直到它是一个排序的列表。在

提前谢谢你。在

Answer 1

数组内容在函数末尾写回alist，而{}在上面的级别中是lefthalf。在

当我从C转换到Python时，我发现这一点非常混乱，但是在Python中，所有的东西都是对对象的引用，，因此所有函数调用都是pass-by-reference。

Answer 2

首先，在lefthalf = alist[:mid]和{}中。它创建了两个新列表：lefthalf和rightlhalf，它们是list中左半整数和右半整数的副本。当你更新这些列表时，列表不会改变。您可以使用以下代码进行测试：

>>> x = [1, 2, 3, 4]
>>> a = x[:2]
>>> a
[1, 2]
>>> b = x[2:]
>>> b
[3, 4]
>>> a[1] = 10
>>> a
[1, 10]
>>> b
[3, 4]
>>> x
[1, 2, 3, 4]

第二，在合并过程中，列表值被就地改变。E、 g.当alist为[54，26]，lefthalf为[54]，rightshalf为[26]，merge将更新alist为[26，54]。这就是为什么调用mergeSort(lefthalf)时lefthalf更改为[26，54]。在

最后，当它调用megeSort(lefthalf)和mergeSort(righthalf)时，由于引用传递，它实际上更新了lefthalf和righthaft。可以使用以下代码进行测试：

^{pr2}$

总之，整个过程是针对给定列表的，它创建了两个新列表：lefthalf和rightshalf。在对lefthalf和rightshalf排序后，通过合并lefthalf和rightshalf更新列表。递归地执行此过程将排序列表。在

如果现在就告诉我。在