Python-为什么我的合并排序版本对输入数组进行破坏性排序？

Question

我正在学习Python和一些基本的数据结构和算法。我实现了自己版本的合并排序，但我不明白为什么它会改变输入数组的顺序。它的行为就像我在mergesort（）函数中将输入数组作为全局引用一样，但我没有这样做。从我实现代码的方式来看，我认为应该在函数的本地范围内对输入数组的副本进行排序，然后返回该副本的排序版本，保持输入数组不变。然而，事实并非如此。它正确地对数组排序；我只是被一个似乎是范围问题的问题弄糊涂了。我将包括代码和示例输出：

arr1 = [38,27,43,3,9,82,10,14] #this will be the input array

def mergesort2(array):
    #print("splitting", array)
    if len(array) > 1:
        middle = len(array)//2
        l = array[:middle]
        r = array[middle:]
        
        mergesort2(l)
        mergesort2(r)
        
        i = j = k = 0
        
        while len(l) > 0 and len(r) > 0:
            if l[0] < r[0]:
                array[k] = l.pop(0)
            else:
                array[k] = r.pop(0)
            k = k + 1
        
        while len(l) > 0:
            array[k] = l.pop(0)
            k = k + 1
        
        while len(r) > 0:
            array[k] = r.pop(0)
            k = k + 1
            
    #print("merging",array)
    return array
    
print("input array before mergesort: ", arr1)
s2 = mergesort2(arr1)
print("input array after mergesort: ", arr1)
print("returned array from mergesort: ", s2)

当我运行上述代码时，我得到以下输出：

input array before mergesort:  [38, 27, 43, 3, 9, 82, 10, 14]
input array after mergesort:  [3, 9, 10, 14, 27, 38, 43, 82]
returned array from mergesort:  [3, 9, 10, 14, 27, 38, 43, 82]

我希望看到输入数组保持不变，并为“s2”分配一个新列表，该列表是输入数组的排序副本。我很感激你能帮助我了解这里发生的一切！

Answer 1

这不是范围问题，而是Python的工作方式。Python通过引用传递列表等对象。也就是说，当您将其作为参数传递给函数时，列表不会被复制。我建议在将其作为参数传递之前复制输入数组。

Answer 2

函数mersort2在array[k]=l.pop（0）和其他类似指令的合并阶段修改其参数数组。如果要创建排序副本，必须分配一个新数组并合并到该数组中，包括参数数组少于2个元素时：

def mergesort2(array):
    res = array[:]
    if len(array) > 1:
        middle = len(array) // 2
        l = mergesort2(array[:middle])
        r = mergesort2(array[middle:])
        i = j = k = 0
        while i < len(l) and j < len(r):
            if l[i] < r[j]:
                res[k] = l[i]
                i = i + 1
            else:
                res[k] = r[j]
                j = j + 1
            k = k + 1
        
        while i < len(l):
            res[k] = l[i]
            i = i + 1
            k = k + 1
        
        # no need to copy remaining elements from r
    return res
    
arr1 = [38,27,43,3,9,82,10,14] #this will be the input array
print("input array before mergesort: ", arr1)
s2 = mergesort2(arr1)
print("input array after mergesort: ", arr1)
print("returned array from mergesort: ", s2)

输出：

input array before mergesort:  [38, 27, 43, 3, 9, 82, 10, 14]
input array after mergesort:  [38, 27, 43, 3, 9, 82, 10, 14]
returned array from mergesort:  [3, 9, 10, 14, 27, 38, 3, 14]