合并排序的比较与排序问题(三)

Question

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

你有两个向量，这个部分应该比较最开始的元素，取较小的元素，然后删除选择的元素，把它放入一个新的向量中。这样做，直到两个向量的大小都为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

代码可以简化：

vector<int> sortit(vector<int> &left, vector<int> &right) {
    vector<int> sorted(left.size() + right.size());
    int i = 0;
    while (1) {
        if (left.at(0) <= right.at(0)) {
            sorted.at(i++) = left.at(0);
            left.erase(left.begin());
            if(left.size == 0){
                do{
                    sorted.at(i++) = right.at(0);
                    right.erase(right.begin());
                }while(right.size != 0);
                return;
            }
        } else {
            sorted.at(i++) = right.at(0);
            right.erase(right.begin());
            if(right.size == 0){
                do{
                    sorted.at(i++) = left.at(0);
                    left.erase(left.begin());
                }while(left.size != 0);
                return;
            }
        }
    }
    return sorted;
}

可以使用索引来代替擦除向量的元素:

vector<int> sortit(vector<int> &left, vector<int> &right) {
    vector<int> sorted(left.size() + right.size());
    int i = 0;
    int ll = 0;
    int rr = 0;
    while (1) {
        if (left[ll] <= right[rr]) {
            sorted[i++] = left[ll++];
            if(ll == left.size){
                do{
                    sorted[i++] = right[rr++];
                }while(rr != right.size);
                break;
            }
        } else {
            sorted[i++] = right[rr++];
            if(rr == right.size){
                do{
                    sorted[i++] = left[ll++];
                }while(ll != left.size);
                break;
            }
        }
    }
    return sorted;
}

Answer 2

不知道如何称呼“比较和订购部分”

常规：合并

对不起，代码很长

使用

first = *left <= *right ? left : right

并操纵它，避免代码复制。

不明白为什么代码忽略了最后一个元素？

left.at(0) <= right.at(0)

和

right.at(0) <= left.at(0)

覆盖所有可能的比较结果（两次相等）：不再计算，否则将计算
按照Msk的建议，将“移动部件”移动到“正确的合并”之后，请注意，初步检查是可有可无的，只需使用“移动循环”即可。

关于你的代码有很多要说的(从注释开始)——参见C merge实现的代码评审。< br >如果您希望在CR@SE上审查您控制的代码，请务必抓住主题，提出一个好问题。

Answer 3

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

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

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

想想当一个数组有(1)而另一个数组有(2，3)时会发生什么，将1加到排序后的向量上，< code>while(left.size()