c++ - 遇到 Mergesort 的比较和排序部分的问题 (c++)

Question

我已经阅读并了解 Mergesort 的工作原理(作为文本)，现在我正在尝试对其进行编码。我已经完成了你划分数据的部分(我使用 vector )直到它的每个大小为 1。现在我已经为 Mergesort 中的另一个必需部分编写了代码，我不知道如何调用它但我只是称之为“比较和排序部分”。

您有 2 个 vector ，这部分应该比较最开始的元素，取较小的元素，然后删除所选元素并将其放入新 vector 中。这样做直到两个 vector 的大小都为 0。

很抱歉代码太长了，但我真的不明白为什么最后一个元素被代码忽略了？ :/ 我已经添加了一些评论，所以也许更容易理解我尝试做的事情。

我尝试作为输入:

vector<int> v1 = {1,4,5,9};
vector<int> v2 = {2,3,6,7,8};

输出:

1 2 3 4 5 6 7 8 0

vector<int> sortit(vector<int> &left, vector<int> &right) {
    vector<int> sorted(left.size() + right.size());
    int i = 0;
    while (left.size() > 0 && right.size() > 0) {
        if (left.at(0) <= right.at(0)) {
            sorted.at(i) = left.at(0);      // putting the smaller element into the new vector
            left.erase(left.begin());       // removing this smaller element from the (old) vector
        }
        else if (right.at(0) <= left.at(0)) {
            sorted.at(i) = right.at(0);     // see comment above
            right.erase(right.begin());     // see comment above
        }
        else if (left.size() <= 0 && right.size() > 0) {    // if left vector has no elements, then take all elements of the right vector and put them into the new vector
            while (right.size() > 0) {
                sorted.at(i) = right.at(0);
                right.erase(right.begin());
            }
        }
        else if (right.size() <= 0 && left.size() > 0) {    // the same just for the right vector
            while (left.size() > 0) {
                sorted.at(i) = left.at(0);
                left.erase(left.begin());
            }
        }
        i++;
    }
    return sorted;
}

Answer 1

检查其中一个数组是否已耗尽以及其他数组是否有剩余元素应该在主 while 循环之外。 因此，请尝试将以下两个支票放在外面。

else if (left.size() <= 0 && right.size() > 0)    

else if (right.size() <= 0 && left.size() > 0)

想想当一个数组有 (1) 和另一个 (2,3) 时会发生什么，在将 1 添加到排序 vector 时，while(left.size() > 0 && right.size() > 0) 条件为假，循环中断。所以其他元素被忽略。