关于c++合并排序代码调试

Question

#include<iostream>
using namespace std;
void MergeSort(int a[],int left,int right);
void Merge(int c[],int d[],int l,int m,int r);
void Copy(int a[],int b[],int left,int right);
main()
{
    cout<<"请输入一组数："<<endl;
    int a[4],b[4];
    for(int i=0;i<4;i++)
    cin>>a[i];
    MergeSort(a,0,3);
    for(int i=0;i<4;i++)
    cout<<a[i]<<" ";
}
void MergeSort(int a[],int left,int right)
{
    if(left<right)//至少有两个个元素 
    {
        int i=(left+right)/2;//取中点 
        MergeSort(a,left,i);
        MergeSort(a,i+1,right);
        int b[4];
        Merge(a,b,left,i,right);//合并到数组b 
        Copy(a,b,left,right);//复制回数组a 
    }
}
void Merge(int c[],int d[],int l,int m,int r)//合并c[l:m]和c[m+1:r]到d[l:r] 
{
    int i=l,j=m+1,k=l;
    while((i<=m)&&(j<=r))
    {
        if(c[i]<=c[j])
        {
            d[k++]=c[i++];
        }
        else
        {
            d[k++]=c[j++];
        }
        if(i>m)
        {
            for(int p=j;p<=r;p++)
            d[k++]=c[p];
        }
        else
        {
            for(int q=i;q<=m;q++)
            d[k++]=c[q];
        }
    }
}
void Copy(int a[],int b[],int left,int right)
{
    for(int i=left;i<=right;i++)
    {
        a[i]=b[i];
        //cout<<b[i]<<endl;
    }
}#include<iostream>
using namespace std;
void MergeSort(int a[],int left,int right);
void Merge(int c[],int d[],int l,int m,int r);
void Copy(int a[],int b[],int left,int right);
main()
{
    cout<<"请输入一组数："<<endl;
    int a[4],b[4];
    for(int i=0;i<4;i++)
    cin>>a[i];
    MergeSort(a,0,3);
    for(int i=0;i<4;i++)
    cout<<a[i]<<" ";
}
void MergeSort(int a[],int left,int right)
{
    if(left<right)//至少有两个个元素 
    {
        int i=(left+right)/2;//取中点 
        MergeSort(a,left,i);
        MergeSort(a,i+1,right);
        int b[4];
        Merge(a,b,left,i,right);//合并到数组b 
        Copy(a,b,left,right);//复制回数组a 
    }
}
void Merge(int c[],int d[],int l,int m,int r)//合并c[l:m]和c[m+1:r]到d[l:r] 
{
    int i=l,j=m+1,k=l;
    while((i<=m)&&(j<=r))
    {
        if(c[i]<=c[j])
        {
            d[k++]=c[i++];
        }
        else
        {
            d[k++]=c[j++];
        }
        if(i>m)
        {
            for(int p=j;p<=r;p++)
            d[k++]=c[p];
        }
        else
        {
            for(int q=i;q<=m;q++)
            d[k++]=c[q];
        }
    }
}
void Copy(int a[],int b[],int left,int right)
{
    for(int i=left;i<=right;i++)
    {
        a[i]=b[i];
        //cout<<b[i]<<endl;
    }
}

输入1 3 2 4得1 2 2 4，不知道哪里有问题，猜测是b[]数组定义有问题？

Answer 1

该回答通过自己思路及引用到各个渠道搜索综合及思考,得到内容具体如下：
在Merge函数中，将两个有序数组合并到一个新数组d[]中，但是在合并过程中，两个for循环的条件判断有误。应该将第一个for循环的条件判断改成 j>r，将第二个for循环的条件判断改成 i>m。修改后的代码如下：

void Merge(int c[],int d[],int l,int m,int r)//合并c[l:m]和c[m+1:r]到d[l:r] 
{
    int i=l,j=m+1,k=l;
    while((i<=m)&&(j<=r))
    {
        if(c[i]<=c[j])
        {
            d[k++]=c[i++];
        }
        else
        {
            d[k++]=c[j++];
        }
    }
    if(j>r)
    {
        for(int p=i;p<=m;p++)
        d[k++]=c[p];
    }
    else
    {
        for(int q=j;q<=r;q++)
        d[k++]=c[q];
    }
}
另外，定义数组b[]的大小应该与数组a[]的大小一致，因此应该将 int b[4] 改为 int b[right-left+1]，即：

void MergeSort(int a[],int left,int right)
{
    if(left<right)//至少有两个个元素 
    {
        int i=(left+right)/2;//取中点 
        MergeSort(a,left,i);
        MergeSort(a,i+1,right);
        int b[right-left+1];
        Merge(a,b,left,i,right);//合并到数组b 
        Copy(a,b,left,right);//复制回数组a 
    }
}
修改后的代码如下：

#include<iostream>
using namespace std;

void MergeSort(int a[],int left,int right);
void Merge(int c[],int d[],int l,int m,int r);
void Copy(int a[],int b[],int left,int right);

int main()
{
    cout<<"请输入一组数："<<endl;
    int a[4],b[4];
    for(int i=0;i<4;i++)
        cin>>a[i];
    MergeSort(a,0,3);
    for(int i=0;i<4;i++)
        cout<<a[i]<<" ";
    return 0;
}

void MergeSort(int a[],int left,int right)
{
    if(left<right)//至少有两个个元素 
    {
        int i=(left+right)/2;//取中点 
        MergeSort(a,left,i);
        MergeSort(a,i+1,right);
        int b[right-left+1];
        Merge(a,b,left,i,right);//合并到数组b 
        Copy(a,b,left,right);//复制回数组a 
    }
}

void Merge(int c[],int d[],int l,int m,int r)//合并c[l:m]和c[m+1:r]到d[l:r] 
{
    int i=l,j=m+1,k=l;
    while((i<=m)&&(j<=r))
    {
        if(c[i]<=c[j])
        {
            d[k++]=c[i++];
        }
        else
        {
            d[k++]=c[j++];
        }
    }
    if(j>r)
    {
        for(int p=i;p<=m;p++)
            d[k++]=c[p];
    }
    else
    {
        for(int q=j;q<=r;q++)
            d[k++]=c[q];
    }
}

void Copy(int a[],int b[],int left,int right)
{
    for(int i=left;i<=right;i++)
    {
        a[i]=b[i];
    }
}

修改后的代码可以正确地对数组进行合并排序。

---

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢