C++ 合并排序返回原始向量

Question

我一直在尝试在 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;
    }
}

Answer 1

首先你应该知道它们之间的区别：

按值传递
按引用传递

去看看here.

其次，您应该如图所示更改代码：

#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 
}

你忘记了主函数中的return语句。
停止使用using namespace std。检查为什么 here
请注意 "\n" 而不是 std::endl。你可以了解更多here

C++ 合并排序返回原始向量

C++ Merge Sort returning original vector

c++

mergesort