我正在尝试将 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,
为什么我会陷入这个循环？
最佳答案
正如评论所指出的，您的数组索引是错误的。
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)
关于c++ - 分割 vector 时无限循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46226963/