c++ - C ++合并排序返回原始向量
问题描述
我一直在尝试使用 C++ 中的向量进行合并排序,并且遇到了一个问题,即任何向量输入都按其原始顺序排序。我在这里基于 geeks4geeks 网站的算法:https ://www.geeksforgeeks.org/merge-sort/
到目前为止,我已经花了大约五个小时试图找到错误的根源,似乎在结束合并函数后,向量会以某种方式恢复到其原始格式,但我不确定为什么。任何建议将不胜感激。
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int> vect, int p, int q, int r) {
int i, j, k, n1, n2;
n1 = q - p + 1;
n2 = r - q;
vector<int> L, R;
L.resize(n1);
R.resize(n2);
for (i = 0; i < n1; i++) {
L[i] = vect[p + i];
}
for (j = 0; j < n2; j++) {
R[j] = vect[q + 1 + j];
}
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
vect[k] = L[i];
i++;
}
else {
vect[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
vect[k] = L[i];
i++;
k++;
}
while (j < n2) {
vect[k] = R[j];
j++;
k++;
}
}
void mergeSort(vector<int> vect, int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergeSort(vect, p, q);
mergeSort(vect, q + 1, r);
merge(vect, p, q, r);
}
}
int main() {
vector<int> vect{4,3,5,6,7,8};
mergeSort(vect, 0, vect.size() - 1);
for (int i = 0; i < vect.size(); i++) {
cout << vect[i] << endl;
}
}
解决方案
首先,您应该知道以下之间的区别:
按值传递
参考传递
去这里检查一下。
其次,您应该更改代码,如下所示:
#include <iostream>
#include <vector>
//using namespace std; forget about it, start using std::whatever_it_is_in_here
void merge(std::vector<int> &vect, int p, int q, int r) // note the & near vect
{
int i, j, k, n1, n2;
n1 = q - p + 1;
n2 = r - q;
std::vector<int> L, R;
L.resize(n1);
R.resize(n2);
for (i = 0; i < n1; i++) {
L[i] = vect[p + i];
}
for (j = 0; j < n2; j++) {
R[j] = vect[q + 1 + j];
}
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
vect[k] = L[i];
i++;
}
else {
vect[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
vect[k] = L[i];
i++;
k++;
}
while (j < n2) {
vect[k] = R[j];
j++;
k++;
}
}
void mergeSort(std::vector<int> &vect, int p, int r) // note the & near vect
{
if (p < r) {
int q = (p + r) / 2;
mergeSort(vect, p, q);
mergeSort(vect, q + 1, r);
merge(vect, p, q, r);
}
}
int main()
{
std::vector<int> vect{4,3,5,6,7,8};
mergeSort(vect, 0, vect.size() - 1);
for (int i = 0; i < vect.size(); i++)
std::cout << vect[i] << "\n"; // note \n instead of std::endl
return 0; // you forgot the return statement
}
推荐阅读
- java - File.delete 不删除文件
- reactjs - NextJS:如何在成功验证后将用户重定向到他们请求的页面?
- reactjs - React 仅渲染从 firebase 下载的列表中的一项
- flutter - 有什么方法可以检查用户是否收到了从 firebase 消息中收到的通知
- redis - 当一个渐进式 rehash 触发器时,redis 如何执行
- arrays - #!/usr/bin/perl,如何将字符串中的关键字与数字匹配
- html - html 属性中的大写字母
- .net - .Net Core API:没有路由匹配提供的值
- vba - ItemAdd 运行了几次然后停止工作,直到我重新启动 Outlook
- api - 如何从外部 JSON 文件中读取测试数据并与邮递员响应进行比较?