我尝试使用简单的情况进行排序
test = {12, 11, 13, 5, 6};
它将左半部分和右半部分的子部分拆分和合并为
{11 12} & {5 6 13}
这是需要的。 但在最终合并期间它需要左半边和右半边作为
{12 11} & {13 5 6}
这给出了错误的答案:
{12 11 13 5 6}
为什么会这样?这是我的代码。
void mergesrt(deque<int> mydeq){
if (mydeq.size() > 1){
int mid = mydeq.size()/2;
deque<int> lefthalf(mydeq.begin(), mydeq.begin() + mid);
deque<int> righthalf(mydeq.begin() + mid, mydeq.begin() + mydeq.size());
mergesrt(lefthalf);
mergesrt(righthalf);
int i = 0;
int j = 0;
int k = 0;
cout << "--------------merging-----------" << endl;
while (i < lefthalf.size() && j < righthalf.size()){
if (lefthalf[i] < righthalf[j]){
mydeq[k] = lefthalf[i];
k++;
i++;
}
else{
mydeq[k] = righthalf[j];
k++;
j++;
}
}
while (i < lefthalf.size()){
mydeq[k] = lefthalf[i];
k++;
i++;
}
while (j < lefthalf.size()){
mydeq[k] = righthalf[j];
k++;
j++;
}
}
return;
}
最佳答案
这里的问题很微妙,新开发者不容易注意到。您正在将您的论点传递给 mergsrt
按值(value),这意味着制作了一份拷贝。排序是在这个拷贝上完成的,并没有改变原来的双端队列。您需要改为通过引用 ( mergsrt(deque<int> &)
) 传递。
关于c++ - 合并排序无法在流程结束时合并零件,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39453689/