C++ 合并排序返回原始 vector

Question

我一直在尝试使用 C++ 中的 vector 进行合并排序，但遇到了一个问题，即任何 vector 输入都按其原始顺序排序。我的算法基于 geeks4geeks 网站:https://www.geeksforgeeks.org/merge-sort/

到目前为止，我已经花了大约五个小时试图找到错误的根源，似乎在结束合并功能后， vector 以某种方式恢复到其原始格式，但我不确定为什么。任何建议将不胜感激。

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

---

1. 您忘记了 main 函数中的return 语句。
2. 停止使用using namespace std。检查原因here
3. 注意 "\n" 而不是 std::endl。可以多了解一下here