0

我正在努力思考以下 C++ 中合并排序的递归实现

让我明白的是，由于向量是通过引用传递的，并且 vec.clear() 被调用，即使在一些合并完成之后，它怎么不会消除向量。例如，当基数被命中时，该函数返回堆栈的顶部帧并继续向下堆栈。但是，该函数需要多次合并，并且在每次合并之前清除向量，我认为这意味着内存中的空间（因为它是通过引用传递）被清除并且我们丢失了已经合并的内容？如果这个方法是按值传递的，我可以理解它是如何工作的，但是这是通过引用传递的，所以我很困惑。

void merge(vector<int> &final, vector<int> &left, vector<int> &right) {
    while (left.size() > 0 || right.size() > 0) {
        if (right.size() == 0) {
            final.push_back(left.at(0));
            left.erase(remove(left.begin(), left.end(), left.at(0)), left.end());
        }
        else if (left.size() == 0) {
            final.push_back(right.at(0));
            right.erase(remove(right.begin(), right.end(), right.at(0)), right.end());
        } else if (left.at(0) <= right.at(0)) {
            final.push_back(left.at(0));
            left.erase(remove(left.begin(), left.end(), left.at(0)), left.end());
        } else if (right.at(0) < left.at(0)) {
            final.push_back(right.at(0));
            right.erase(remove(right.begin(), right.end(), right.at(0)), right.end());
        }
    }
}

void sort(vector<int> &vec) {
    int n = vec.size();

    // BASE CASE
    if (n <= 1) {
        return;
    }

    // GENERAL CASE / RECURSIVE CASE
    vector<int> leftVec;
    vector<int> rightVec;

    for (int i = 0; i < n; i++) {
        if (i < n / 2) {
            leftVec.push_back(vec.at(i));
        } else {
            rightVec.push_back(vec.at(i));
        }
    }

    sort(leftVec);
    sort(rightVec);
    vec.clear();
    merge(vec, leftVec, rightVec);
}
4

1 回答 1

2

的内容vec已被复制到调用之前和leftVec调用之前，因此没有任何信息丢失。您没有给出源代码，但我们可以假设它会将内容复制回.rightVecclearmergevec

于 2013-03-09T04:14:11.180 回答