我正在尝试在 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
和更改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++];
}
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句