这是解释 MergeSort 伪代码的正确方法吗？ return 在这里做什么？

Question

在不同的网站上伪代码类似于下面这个：

merge_sort(num_list)
length <-- length of num_list

if length > 1

    shorter_list_A <-- first half of num_list
    shorter_list_B <-- second half of num_list

    result_A <-- merge_sort(shorter_list_A)
    result_B <-- merge_sort(shorter_list_B)

    sorted_list <-- merge(result_A, result_B)

    return sorted_list
else
    return num_list
end

所以如果我们有 4 个数字：8,3,6,2

MergeSort(8,3,6,2)

前半部分数字放在Shorter_list_A(8,3) 和数字的后半部分 Shorter_list_B(6,2)

    shorter_list_A <-- first half of num_list
    shorter_list_B <-- second half of num_list

所以我们现在有两个列表：shorter_list_A(8,3) 和 Shorter_list_B (6,2)

    result_A <-- merge_sort(shorter_list_A)

Merge_sort 再次调用 merge_sort，所以发生了什么：

merge_sort(Shorter_list_A)  // also 8,3
length <-- length of Shorter_list_A

if length > 1

    shorter_list_A <-- first half of Shorter_list_A 
//8 put to Shorter_list_A
    shorter_list_B <-- second half of Shorter_list_A
//3 put to Shorter_list_B

    result_A <-- merge_sort(shorter_list_A)
//merge_sort calls merge_sort again
    result_B <-- merge_sort(shorter_list_B)

    sorted_list <-- merge(result_A, result_B)

    return sorted_list
else
    return Shorter_list_A
end

现在我们又有了两个列表：shorter_list_A(8) 和 Shorter_list_B (6)

从目前的解释来看，我的理解是正确的还是完全错误的？

然后它再次调用 merge_sort。由于 Shorter_list_A 的长度仅为 1，因此它只包含一个数字 8。发生的情况是：

merge_sort(Shorter_list_A)
length <-- length of Shorter_list_A
    return Shorter_list_A
end

它returns Shorter_list_A，也就是8。

return 在这里具体做什么？我被困在那里了。

Answer 1

你必须记住它向下递归 short_list_A 直到它得到条件 length <= 1 当你 return 从递归调用它 returns 到上一个调用在调用堆栈中，看起来像：

result_A <-- merge_sort(shorter_list_A) 
// *** return here ***
result_B <-- merge_sort(shorter_list_B)
sorted_list <-- merge(result_A, result_B)
return sorted_list

因此它对 result_B 执行相同的操作，然后在 return调用堆栈之前合并结果。

举个小例子，缩进表示递归深度：

merge_sort([4,7,2,3,1,8,6,5])
    a = merge_sort([4,7,2,3])
        a = merge_sort([4,7])
            a = merge_sort([4])   // Doesn't recurse anymore length <= 1
            b = merge_sort([7])
            r = merge(a,b) = merge([4], [7])
            return r = [4,7]
        b = merge_sort([2,3])
            a = merge_sort([2])
            b = merge_sort([3])
            r = merge(a, b) = merge([2], [3])
            return r = [2,3]
        r = merge(a,b) = merge([4,7], [2,3])
        return r = [2,3,4,7]
    b = merge_sort([1,8,6,5])
        a = merge_sort([1,8])
            a = merge_sort([1])
            b = merge_sort([8])
            r = merge(a, b) = merge([1],[8])
            return r = [1,8]
        b = merge_sort([6,5])
            a = merge_sort([6])
            b = merge_sort([5])
            r = merge(a, b) = merge([6],[5])
            return r = [5,6]
        r = merge(a,b) = merge([1,8], [5,6])
        return r = [1,5,6,8]
    r = merge(a, b) = merge([2,3,4,7], [1,5,6,8])
    return r = [1,2,3,4,5,6,7,8]

希望对您有所帮助。

Answer 2

每个 return 都会向调用者发回一个 排序的 列表，其中包含它作为输入接收到的元素。

在最底层，当只有一个元素时，列表默认排序并returned。当您将在 result_A 和 result_B 中获得一个元素的两个排序列表时，您将它们都传递给 merge() 方法，现在这个方法会完成繁重的工作。这将获取两个列表并将它们合并以提供一个新列表，其中包含按排序顺序排列的两个列表的元素。

Merge()长什么样子？

Merge() 将实例化一个新列表。我们称它为 sorted_list 然后它将开始从它作为输入获得的两个列表的 head 中读取，并将在 head 位置取两个元素的最小值并将其放入 sorted_list 它刚刚创建。该方法将继续使用两个输入列表的 head 直到它们都完成。现在，两个列表的合并按排序顺序出现在 sorted_list 中。我假设您希望列表从最小到最大排序。

运行通过你的例子

在最后一层，对于单个元素，head -> 8 -> null 的第一个列表和 head -> 3 -> null 的第二个列表将合并形成 head -> 3 -> 8 -> null

在这一层本身，它将head -> 6 -> null和head -> 2 -> null两个列表合并为head -> 2 -> 6 -> null

将底层称为 0。在 0 层，您只有单个元素。在第 1 级，您将拥有两个元素的列表。在第 2 级，您将合并两个包含 2 个元素的列表以提供一个列表。

所以，从 head -> 3 -> 8 -> null 和 head -> 2 -> 6 -> null，你会得到 head -> 2 -> 3 -> 6 -> 8 -> null。

最终将return编辑此列表。没有进一步上升的水平。这是您获得原始未排序输入列表的级别，因此在此 return，实际上您将 return 排序列表给调用者。

总结

Level num_list Shorter_List_A Shorter_List_B Result_A Result_B sorted_list

2     8,3,6,2  8,3            6,2            3,8      2,6      2,3,6,8

1(a)  8,3      8              3              8        3        3,8  
1(b)  6,2      6              2              6        2        2,6

0(a)  8        -              -              -        -        8
0(b)  3        -              -              -        -        3 
0(c)  6        -              -              -        -        6
0(d)  2        -              -              -        -        2

因此，我们从级别 2 开始。在级别 1(a)、1(b) 递归调用自己。然后从 level 1 在 level 0(a), 0(b), 0(c), 0(d) 再次递归地调用我们自己，然后将合并的结果再次冒泡到 level 2 然后 return编辑了一个排序列表。

这是解释 MergeSort 伪代码的正确方法吗？ return 在这里做什么？

Is this the right way to explain MergeSort pseudocode? What return does here?

return

mergesort

pseudocode