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 的“calls”参数，并将其传递给每次递增 1 的函数，并在所有打印语句中提供它 - 这允许您查看每个调用来自哪些语句，让您看到该函数在最后展开。