无法在 C++ 中实现 Mergesort 算法，向量的语法

Question

我正在尝试在 cpp 中实现合并排序，但我在使用向量的正确语法方面遇到了一些问题，尤其是 for 循环中我合并元素的部分。一些帮助将不胜感激。到目前为止，我的代码给出了错误的输出。此外，我想知道是否可以修改此代码以计算倒置，每次我进入 else 情况时，倒置都会增加但它缺少极端情况。我尝试将 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;
}

无法在 C++ 中实现 Mergesort 算法，向量的语法

Trouble implementing Mergesort algorithm in c++, syntax of vectors

c++

syntax

mergesort

vector