c++ - 合并排序无法在流程结束时合并零件

Question

我尝试使用简单的情况进行排序

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

Answer 1

这里的问题很微妙，新开发者不容易注意到。您正在将您的论点传递给 mergsrt按值(value)，这意味着制作了一份拷贝。排序是在这个拷贝上完成的，并没有改变原来的双端队列。您需要改为通过引用 ( mergsrt(deque<int> &) ) 传递。