合并排序中的递归调用

Question

运行合并排序并打印左侧部分为我提供了给定输入的以下输出，我无法理解为什么它在最后打印 2。请帮我看看这个递归调用是怎样的

输入：（数组大小，下一行是数组）

5 
8 5 4 2 1

输出为

这是我的完整代码供参考，它是非常标准的算法所以只需检查 mergesort 函数并查看我要打印的内容。

#include <bits/stdc++.h>

using namespace std;

vector<int> merge(vector<int>&B, vector<int>&C) {
    int n = B.size() + C.size();
    vector<int> D(n);
    for (int t{}; t < n; t++)
        D[t] = 0;
    int i{}, j{}, k{};
    
    while (i < B.size() && j < C.size()) {
        if (B[i] < C[j]) {
            D[k] = B[i];
            i++;
            k++;
        } else {
            D[k] = C[j];
            j++;
            k++;
        }
    }
    if (i < B.size()) {
        while (i < B.size()) {
            D[k] = B[i];
            k++;
            i++;
        }
    } else {
        while (j < C.size()) {
            D[k] = C[j];
            k++;
            j++;
        }
    }
    return D;
}

vector<int> merge_sort(vector<int> &A, int left, int right) {
    vector <int> B, C, A_;
    if (left == right) {
        A_.push_back(A[left]);  
        return A_;
    }
    int m = (left + right) / 2; //possible error, convert this to int then
    B = merge_sort(A, left, m);

    for (int i{}; i < B.size(); i++)
        cout << B[i] << " ";
    cout << endl;

    C = merge_sort(A, m + 1, right);
    A_ = merge(B, C);
    return A_;
}

int main() {
    int n; 
    cin >> n;
    vector<int> vec(n);
    for (int i{}; i < n; i++)
        cin >> vec[i];
    vector<int> sorted_vec = merge_sort(vec, 0, vec.size() - 1);
    
    for (int i{}; i < n; i++)
        cout << sorted_vec[i] << " ";
    cout << endl;
    
    return 0;
}

Answer 1

那是因为在深度优先访问中，您仅在向量的左侧（对于每个递归调用）调用 cout：您始终打印左侧发生的情况，并且仅针对左侧节点（以及左侧之后）已排序）。这张图应该可以帮助你理解：

85421 代表您第一次拨打 merge_sort。那里有矢量 B (854) 和矢量 C (21)
- 然后您在 854 上调用 merge_sort。这里有向量 B (85) 和向量 C (4)
  - 然后您在 85 上调用 merge_sort。这里有向量 B (8) 和向量 C (5)
    - 具有一个元素的向量已排序。
  - 你打印 B 向量 (8)
  - 您在 (5) 致电 merge_sort
    - 具有一个元素的向量已排序。
  - 你合并 (8) 和 (5) 得到 (58)
  - 你return(58)作为B来调用方法
- 你打印 B 向量 (58)
- 您在 (4) 致电 merge_sort
  - (4) 已经排序
- 您将 (58) 和 (4) 合并到 (458) 并将 return (458) 作为 B 合并到调用方法
你打印 B 向量 (458)
您对 (21) 向量 B 是 (2) 并且向量 C 是 (1) 调用归并排序
- 在 (2) 上调用归并排序，然后在调用方方法上作为 B 返回 (2)
- 你打印 (2)
- 您在 (1)
- 您将 (2) 和 (1) 合并为 (12) 并将 (12) 作为 C 发送回调用方方法
你合并 (458) 和 (12) 和 (12458) 是结果。
你在 main
中打印 (12458)

希望这对您有所帮助:)

合并排序中的递归调用

Recursion calls in Merge sort

c++

algorithm

mergesort