当向量大小不是 2^n 时，合并排序功能不起作用

Question

我想在这个问题前说一下我是 c++ 的初学者。

为了练习，我尝试使用所学的基础知识创建一个合并排序函数。代码如下：

#include <bits/stdc++.h>
using namespace std;

vector<int> mergesort(vector <int> x);
int main(){
    vector<int> tosort={1,9,0};
    tosort=mergesort(tosort);
    for(int  i=0; i<tosort.size(); i++){
        cout<<tosort[i]<<" ";
    }

}
vector<int> mergesort(vector <int> x){
   if (x.size()==1){
       return x ;
   }
   else{
       int vsize=x.size();
       vector<int> halfv1(x.begin(),x.begin()+ceil(vsize / 2));
       vector<int> halfv2(x.begin()+ceil(vsize / 2),x.end());
       
       
       halfv1=mergesort(halfv1);
       halfv2=mergesort(halfv2);
       int counter1=0;
       int counter2=0;
       while(counter1+counter2<vsize){
           if(counter1==ceil(vsize / 2)){
               for(int i=counter1+counter2;i<vsize;i++){
                   x[i]=halfv2[counter2];
                   counter2++;
               }


           }
           if(counter2==floor(vsize / 2)){
               for(int i=counter1+counter2;i<vsize;i++){
                   x[i]=halfv1[counter1];
                   counter1++;
               }

           }
           if(counter1 !=ceil(vsize / 2) && counter2 !=floor(vsize / 2)){
               if(halfv1[counter1 ]<=halfv2[counter2]){
                   x[counter1+counter2]=halfv1[counter1];
                   counter1++;
               }
               else{
                   x[counter1+counter2]=halfv2[counter2];
                   counter2++;
               }
           }
       }
       return x;
   }
}

当要排序的向量的大小为 2^n 时，代码可以正常工作。但是，如果不是，则输出是错误的。例如，在上面的示例中，输出是 0 1 0。请您帮我找出问题所在。

我尝试逐行处理逻辑，似乎没有错误。我怀疑我不知道的知识存在问题。

考虑到我是初学者，请您帮助我。我也知道可能有更有效的方法来编写代码，但我只是想用我目前的知识来练习我的算法技能，并在这里找到我的理解差距。

非常感谢您的帮助。

Answer 1

直接的问题是

halfv2

的大小不是

floor(vsize / 2)

而是

vsize - vsize / 2

（或

(vsize + 1) / 2)

），因此您需要更改所有这些比较，以免访问越界索引。 （请注意，

ceil

仅适用于

vsize / 2

的截断结果。）