c++ - 分割 vector 时无限循环

Question

我正在尝试将 MergeSort 实现为家庭作业。我得到了一个名为 MergeSort 的函数，它接受一个输入 vector 。然后，我得到了拆分和合并功能。

我知道 MergeSort 是如何工作的，我也用 Java 实现过多次，但我一直使用数组，我对指针和引用没有太多经验。

这是我目前的情况，

void Split(const std::vector<int>& input, std::vector<int>* output1, std::vector<int>* output2) {



    std::cout << "In split function" << std::endl;
    // this just prints the values in my vector
    for (int i = 0; i < input.size(); i++) {
        std::cout << input[i] << ", ";
    }
    std::cout << std::endl;

    if (input.size() > 1) {


        int i = 0;
        int j = input.size();

        while (i <= j) {
            output1->push_back(input[i]);
            i++;


            if (i != j) {
                output2->push_back(input[j]);
                j--;
            }
        }



        std::vector<int> left= {};
        std::vector<int> right = {};

        Split(*output1, &left, &right);
        Split(*output2, &left, &right);
    }
}

void MergeSort(std::vector<int>* input){
    std::vector<int> output1= {};
    std::vector<int> output2 = {};
    std::cout << "Starting mergesort" << std::endl;
    Split(*input, &output1, &output2);

}

我还有一个合并函数，我不想包含它，因为它与我的问题无关。

现在，我的代码可以编译，但它陷入了无限循环并给我一个段错误。

我有一个调用 MergeSort 函数的主函数，其值为:{3, 5, 1, 2, 9, 4}

调用 Split 函数，然后将其打印到标准输出直到终止:

在分割函数中
3, 5, 1,


为什么我会陷入这个循环？

Answer 1

正如评论所指出的，您的数组索引是错误的。

int i = 0;
int j = input.size();

因此，您的循环最终生成 output1 为 {3, 5, 1}，然后将其馈送到 Split(.. .)，再次生成 {3, 5, 1}，直到递归导致段错误。

int i = 0;
int j = input.size() - 1; 

这将导致 output1 数组实际上收缩 {3, 5}，导致在 if(input.size() > 1)