难以在C ++中实现Mergesort算法，向量语法

Question

我正在尝试在cpp中实现mergesort，我在使用矢量正确的语法时遇到了一些麻烦，特别是在for循环中要合并元素的部分。一些帮助，将不胜感激。到目前为止，我的代码给出了错误的输出。另外，我想知道是否可以修改此代码以计算反转，所以每次我在其他情况下，反转都会增加，但是缺少缺角情况。我尝试将v[i] = left[i1]设置为v.insert(v.begin() + i, left.at(i1))，这也没有用，我通常对向量的[]运算符感到困惑，它与数组[]运算符有何不同？

#include <bits/stdc++.h>

using namespace std;

void mergeSort(vector<int>& v) {
    if(v.size() > 1) {
        vector<int> left(v.begin(), v.begin() + v.size()/2);  
        vector<int> right(v.begin() + v.size()/2, v.end());

        mergeSort(left);
        mergeSort(right);

        int i1 = 0;
        int i2 = 0;

        for(int i = 0; i < v.size(); i++) {
            if(i2 >= right.size() || (i1 < left.size() && left[i] < right[i])) {
                v[i] = left[i1]; i1++;
            } else {
                v[i] = right[i2]; i2++;
            }
        }       
    }   
}

int main() {
    vector<int> v = {22, 18, 12, -4, 58, 7, 31, 42};
    mergeSort(v);
    for(auto i = v.begin(); i != v.end(); i++) cout << *i << endl;
    return 0;
}

Answer 1

[我认为您的条件是错误的（您将向量的元素与索引为i进行比较），请尝试此操作（我还根据您的要求添加了反转检查）。我只是将索引的名称分别从i2和i1更改为r和l。

for (int i = 0; i < v.size; i++) {
    if (r < right.size() && (right[r] <= left[l] || l >= left.size)) {
        if (right[r] < left[l]) inversions++; 
        v[i] = right[r++];  
    } else {
        v[i] = left[l++];
    }    
}

Answer 2

您的条件不正确。您需要使用i1和i2索引，因为i很快超出了right的大小（我已通过调试器进行了检查，您也应该使用它！）这是我的完整解决方案和一些其他测试：

//#include <bits/stdc++.h>
#include <vector>
#include <iostream>

using namespace std;

void mergeSort(vector<int>& v) {
    if (v.size() > 1) {
        vector<int> left(v.begin(), v.begin() + v.size() / 2);
        vector<int> right(v.begin() + v.size() / 2, v.end());

        mergeSort(left);
        mergeSort(right);

        int i1 = 0;
        int i2 = 0;

        for (int i = 0; i < v.size(); i++) {
            if (i2 >= right.size() || (i1 < left.size() && left[i1] < right[i2])) {
                v[i] = left[i1]; i1++;
            }
            else {
                v[i] = right[i2]; i2++;
            }
        }
    }
}

void printVector(vector<int>& v)
{
    for (auto i = v.begin(); i != v.end(); i++) cout << *i << ' ';
    std::cout << std::endl;
}

void test(vector<int>& v)
{
    std::cout << "------\n";
    printVector(v);
    mergeSort(v);
    std::cout << "------\n";
    printVector(v);
    std::cout << "------\n";
}

int main() {
    vector<int> v1 = { 22, 18, 12, -4, 58, 7, 31, 42 };
    vector<int> v2 = { 10 };
    vector<int> v3 = { 10 , 20 };
    vector<int> v4 = { 20 , 10 };
    vector<int> v5 = { 20 , 10 , 5};
    vector<int> v6 = { 10 , 10 , 10 };
    vector<int> v7 = { 11 , 10 , 10 };
    vector<int> v8 = { };
    test(v1);
    test(v2);
    test(v3);
    test(v4);
    test(v5);
    test(v6);
    test(v7);
    test(v8);
    return 0;
}