c++ - 使用向量在 C++ 中合并排序实现
问题描述
我正在尝试使用 C++ 中的向量实现合并排序,这是我正在执行的以下代码:
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int> &a, int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++) {
L[i] = a[l + i];
}
for (j = 0; j < n2; j++) {
L[j] = a[m + 1 + j];
}
i = 0;
j = 0;
k = l; //merged array
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
a[k] = L[i];
i++;
} else {
a[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
a[k] = L[i];
i++;
k++;
}
while (j < n2) {
a[k] = R[j];
j++;
k++;
}
}
void mergeSort(vector<int> &a, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(a, l, m);
mergeSort(a, m + 1, r);
merge(a, l, m, r);
}
}
int main() {
int n;
std::cin >> n;
vector<int> a(n);
for (int i = 0; i < a.size(); i++) {
cin >> a[i];
}
mergeSort(a, 0, a.size() - 1);
for (int i = 0; i < a.size(); i++) {
cout << a[i];
}
}
当我执行此操作并输入任何值时,我会在数组中返回垃圾值,a[i] = 7405024
代码是否由于我无法就地更改向量的值或还有其他原因而给我错误。
解决方案
问题出在merge
函数中
for(j=0;j<n2;j++)
{
R[j]=a[m+1+j]; // not L[j]
}
当您使用向量实现时,建议也更改L
向量R
。默认情况下,C++ 不支持 VLA。一些编译器可能会接受,但应该完全避免使用。
std::vector<int> L(n1);
std::vector<int> R(n2);
推荐阅读
- android - 尝试通过适配器从片段添加项目时,微调器和 ViewPager2 显示为空白
- python-3.x - 拆分列表的值
- c++ - 在多个系统上使用 CMake 安装 C++ 应用程序
- ios - 更改 leftBarButtonItem 位置。它离边境很远
- java - GraalVM / Quarkus ; 构建本机应用程序时冻结
- java - OAuth2 Spring boot缺少必需的“用户名
- javascript - 如何使用事件委托删除本地存储的数组中的项目?
- perl - 即使未初始化,如何检测包中是否存在(已声明)词法变量?
- swift - 在 SwiftUI 中创建共享按钮时需要帮助
- git - 为什么空的 Bitbucket 存储库“包含”我“本地没有”的工作?