理解递归合并排序过程背后的直觉 [英] Understanding the intuition behind recursive merge sort procedure

问题描述

我对以下代码的以下输出感到困惑:

I'm confused on the following output for the following code:

def msort3(x):
    print("splitting:",x)
    result = []
    if len(x) < 2:
        print("merging:",x)
        return x

    mid = int(len(x) / 2)
    y = msort3(x[:mid])
    print(y)
    z = msort3(x[mid:])  ## this will be run when x is 87
    print(z)
    i = 0
    j = 0
    while i < len(y) and j < len(z):
        if y[i] > z[j]:
            result.append(z[j])
            j += 1
        else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
    print("result is ", result)
    return result


if __name__ == '__main__':
     print("hi", msort3([17,87,6,22]))

部分输出是:

splitting: [17, 87, 6, 22]
splitting: [17, 87]
splitting: [17]
merging: [17]
[17]
splitting: [87]
merging: [87]
[87]
result is  [17, 87]
[17, 87]
splitting: [6, 22]

现在它是如何读取[6, 22]的?当我们得到 result = [ 17,87] 时，我认为到那时递归调用已经完成.

Now how did it read [6, 22]? I thought by then the recursion calls are already done when we got result = [ 17,87].

请帮忙，我很困惑，已经在这里跟踪代码 http://interactivepython.org/courselib/static/pythonds/SortSearch/TheMergeSort.html.

Please help, I'm very confused and already tracked the code here http://interactivepython.org/courselib/static/pythonds/SortSearch/TheMergeSort.html.

推荐答案

正常运行；result is [17, 87] 您看到的打印是子调用的中间结果，而不是最终结果.递归的工作原理是将问题分解为更小的块并计算这些子问题的子结果，然后将结果通过调用堆栈传回原始调用者，并在此过程中合并子问题的结果.

That's working normally; the result is [17, 87] print you're seeing is an intermediate result of a child call, not the final result. Recursion works by breaking the problem into smaller chunks and computing sub-results for these sub-problems, then passing the results back through the call stack towards the original caller, merging results of the sub-problems along the way.

在递归中添加缩进可以帮助说明这个过程:

Adding indentation to the recursion can help illustrate the process:

[17, 87, 6, 22] <-- split
    [17, 87] <-- split
        [17]
        [87]
    [6, 22] <-- split
        [6]
        [22]

在向下的过程中，[17, 87] 数组将在 [6, 22] 被检查和合并之前被完全检查和合并.在备份调用栈的路上:

On the way down, the [17, 87] array will be entirely examined and merged before [6, 22] is examined and merged. On the way back up the call stack:

        [17]
        [87]
    [17, 87] <-- merge
        [6]
        [22]
    [6, 22] <-- merge
[6, 17, 22, 87] <-- merge

这里，[17, 87] 等待 [6, 22] 调用完全解析，剩下的 [6, 17, 22,87] 合并在深度 0 处，是最终结果.

Here, [17, 87] waits for the [6, 22] call to resolve completely, and the remaining [6, 17, 22, 87] merge is at depth 0 and is the final result.

您的示例也可能令人困惑，因为子数组 [17, 87] 和 [6, 22] 已经排序，因此唯一具有任何后果的合并位于 [17, 87] 和 [6, 22] 之间的深度 0.我建议尝试一些不同的值，看看是否有助于点击.

Your example may also be confusing because the sub arrays [17, 87] and [6, 22] are already sorted, so the only merge that has any consequence is at depth 0 between [17, 87] and [6, 22]. I recommend trying some different values to see if that helps make it click.

使用缩进技巧帮助看"递归可以通过添加 depth 参数来完成(为了空间/易于阅读，我还稍微缩短了您的代码):

Using the indentation trick to help "see" the recursion can be done by adding a depth parameter (I also shortened your code a bit for space/ease of reading):

def msort3(x, depth):
    result = []

    if len(x) < 2: 
        print(" " * depth + "single:",x)
        return x
    else:
        print(" " * depth + "splitting:",x)

    mid = len(x) // 2
    l = msort3(x[:mid], depth + 4)
    r = msort3(x[mid:], depth + 4)

    while l and r:
        if l[0] < r[0]:
            result.append(l.pop(0))
        else:
            result.append(r.pop(0))

    result += l + r
    print(" " * depth + "merged:", result)
    return result

print("\ndone:",msort3([17,87,6,22], 0))

输出:

splitting: [17, 87, 6, 22]
    splitting: [17, 87]
        single: [17]
        single: [87]
    merged: [17, 87]
    splitting: [6, 22]
        single: [6]
        single: [22]
    merged: [6, 22]
merged: [6, 17, 22, 87]

done: [6, 17, 22, 87]

这篇关于理解递归合并排序过程背后的直觉的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！