python - 合并排序继续调用自身，尽管有条件

Question

我遇到了一个非常奇怪的问题，自学写作。我用 Python 做了这个合并排序。

我想知道您能否帮助我理解为什么尽管满足关闭函数的条件，它仍会继续调用自身。

print arrayToSort 
#[[67], [26], [75], [80], [54], [93], [97], [96], [77], [91]]

def merge_sort(array):
    newTotalArray = []
    for x in range(0, len(array)/2):
        newSubArray = []
        lowerX = x*2
        upperX = x*2+1
        while len(array[lowerX]) > 0 or len(array[upperX]) > 0:
            if len(array[lowerX]) > 0 and len(array[upperX]) > 0:
                if array[lowerX][0] <= array[upperX][0]:
                    newSubArray.append(array[lowerX][0])
                    del array[lowerX][0]
                else:
                    newSubArray.append(array[upperX][0])
                    del array[upperX][0]
            elif len(array[lowerX]) > 0:
                newSubArray.append(array[lowerX][0])
                del array[lowerX][0]
            else:
                newSubArray.append(array[upperX][0])
                del array[upperX][0]
        newTotalArray.append(newSubArray)
    if len(array) % 2 != 0:
        newTotalArray.append(array[len(array)-1])
    print 'still going'
    print newTotalArray
    if len(newTotalArray) > 1:
        merge_sort(newTotalArray)
    print 'finished'
    print newTotalArray

merge_sort(arrayToSort)

我希望这个函数在 len(newTotalArray) == 1 时停止调用自身。

但是，对于这段代码，我得到了

[[67], [26], [75], [80], [54], [93], [97], [96], [77], [91]]
still going
[[26, 67], [75, 80], [54, 93], [96, 97], [77, 91]]
still going
[[26, 67, 75, 80], [54, 93, 96, 97], [77, 91]]
still going
[[26, 54, 67, 75, 80, 93, 96, 97], [77, 91]]
still going
[[26, 54, 67, 75, 77, 80, 91, 93, 96, 97]]
finished
[[26, 54, 67, 75, 77, 80, 91, 93, 96, 97]]
finished
[[], []]
finished
[[], [], []]
finished
[[], [], [], [], []]

我需要将它放入模块并返回结果，但如果我这样做，结果是 [[], [], [], [], []]

你能帮我理解为什么会这样吗？

Answer 1

问题是 python 修改列表而不是列表的副本(这是通过引用传递而不是通过值传递)。因此，每次您删除一个条目时，您都会将其从原始列表中删除，从而留下您的列表。它不是仍在调用，它只是在完成先前的值。额外的“空”数组来自末尾的 print 语句，而不是前面的。这些与提供的数组具有相同长度但为空的事实告诉您此删除是在原始数组上发生的。

例如:

def mess_with_array(array):
    for i in range(2,len(array)):
        del array[2]

test = [1,2,3,4,5,6]
mess_with_array(test)
print test

结果在 [1,2] 中。这是因为我们修改了原来的数组。

诀窍是要么返回值(如果您不关心原始数组)，要么使用副本并返回值。

改变

if len(newTotalArray) > 1:
    merge_sort(newTotalArray)

到

if len(newTotalArray) > 1:
    return merge_sort(newTotalArray)
else: return newTotalArray

并用

运行函数

arrayToSort = merge_sort(arrayToSort)

或者如果您希望使用副本并保留原始数组，请调用

sortedArray = merge_sort(arrayToSort[:])

这种按引用传递与按值传递的问题很微妙，如果您不小心，它会严重伤害您。在处理一门新语言时，我首先要寻找的是它的传递方式。

一个额外的提示(以及我是如何找出问题所在的)。使用递归函数时，添加一个默认值为 0 的“调用”参数，并将其传递给每次递增 1 的函数，并在所有打印语句中提供它 - 这使您可以查看每次调用的语句, 并让您看到该函数在最后展开。