在 C++ 中实现合并排序算法的麻烦,向量的语法

Xgh05t

我正在尝试在 cpp 中实现合并排序,我在使用向量的正确语法方面遇到了一些麻烦,特别是我正在合并元素的 for 循环内的部分。一些帮助将不胜感激。到目前为止,我的代码给出了错误的输出。另外,我想知道是否可以修改此代码以计算倒数,每次我进入 else 情况时,倒数都会增加,但缺少极端情况。我尝试做v[i] = left[i1]as 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;
}
斯泰瑞克斯

我认为你的条件是错误的(你将向量的元素与 index 进行比较i),试试这个(我还添加了反转检查,正如你所问的)。我只是分别将索引的名称从i2更改i1rl

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++];
    }    
}

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章