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

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，这意味着已制作副本。排序是在这个副本上完成的，并没有改变原来的双端队列。您需要通过引用传递 (mergsrt(deque<int> &))。

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

Merge Sorting fails to merge parts at the end of process

c++

sorting

algorithm

mergesort

data-structures