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

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
[[], [], [], [], []]

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

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

Answer 1

您的 "finished" 语句多次出现错误。一个简单的解决方法是 return 在递归函数到达该行之前控制它。在此 if 块中插入 return 关键字：-

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

顺便说一下，像 array[len(array)-1] 这样的代码冒犯了我。请改用此表格：-

if len(array) % 2 != 0:
    newTotalArray.append(array[-1])

最后一个想法。应避免递归，因为就使用的内存而言，它在运行时昂贵。使用 del array[0] 关键字从数组开头删除元素的效率也低于删除最后一个元素。这是 Python 中的一个更简单的合并排序实现，它避免了递归，也避免了 always 删除临时列表中的第一个元素：-

def merge_sort(array):
    print 'Original: ', array
    array = map(lambda x: [x], array)
    print 'Nested: ', array
    while len(array) > 1:
        for i in xrange(len(array)-2,-1,-2):
            newArray = []
            arrayA, indexA = array[i], 0
            arrayB, indexB = array[i+1], 0
            while indexA < len(arrayA) and indexB < len(arrayB):
                if arrayA[indexA] < arrayB[indexB]:
                    newArray.append(arrayA[indexA])
                    indexA += 1
                else:
                    newArray.append(arrayB[indexB])
                    indexB += 1
            if indexA < len(arrayA):
                newArray += arrayA[indexA:]
            if indexB < len(arrayB):
                newArray += arrayB[indexB:]
            array[i] = newArray
            del array[i+1]
        print 'Step: ', array
    return array[0]

arrayToSort = [93, 64, 16, 28, 65, 80, 42, 96, 8, 44, 1]
print merge_sort( arrayToSort )
#Original:  [93, 64, 16, 28, 65, 80, 42, 96, 8, 44, 1]
#Nested:  [[93], [64], [16], [28], [65], [80], [42], [96], [8], [44], [1]]
#Step:  [[93], [16, 64], [28, 65], [42, 80], [8, 96], [1, 44]]
#Step:  [[16, 64, 93], [28, 42, 65, 80], [1, 8, 44, 96]]
#Step:  [[16, 64, 93], [1, 8, 28, 42, 44, 65, 80, 96]]
#Step:  [[1, 8, 16, 28, 42, 44, 64, 65, 80, 93, 96]]

#[1, 8, 16, 28, 42, 44, 64, 65, 80, 93, 96]

Answer 2

问题是 python 修改列表而不是列表的副本（这是通过引用传递而不是通过值传递）。因此，每次您删除一个条目时，您都会将其从原始列表中删除，从而留下您的列表。它不是仍在调用，它只是在完成先前的值。额外的 "empty" 数组来自末尾的 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]。这是因为我们修改了原数组。

诀窍是 return 值（如果您不关心原始数组），或者使用副本和 return 值。

改变

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 的函数，并在所有打印语句中提供它 - 这可以让您看到哪些语句来自每次调用，并让您看到函数在最后展开。

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

Merge sort continues calling itself, despite condition

python

recursion

mergesort