关于归并排序的一个小问题
自己的代码如下：但是运行结果一直不对，不知道哪里有bug
#include <iostream>
using namespace std;
void Merge(int a[],int b[],int i,int m,int n)
{
//将有序的a[i...m]和a[m+1...n]归并为有序的b[i...n]
int k = i,j = m+1;
while(i <= m && j <= n)
{
if (a[i] <= a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}
while(i<=m)
b[k++] = a[i++];
while(j<=n)
b[k++] = a[j++];
}
void MSort(int a[],int b[],int low,int high)
{
//将a[low...high]归并排序为b[low...high]
int m;
if (low == high)
b[low] = a[low];
else
{
m = (low + high)/2;
MSort(a,b,low,m);
MSort(a,b,m+1,high);
Merge(a,b,low,m,high);
}
}
int main()
{
int Test[5] = {5,4,1,2,8};
int Goal[5] ={0};
for (int i = 0;i < 5;i++)
{
cout<<Test[i]<<" ";
}
MSort(Test,Goal,0,4);
cout<<endl;
for (int i = 0;i< 5;i++)
{
cout<<Goal[i]<<" ";
}
cout<<endl;
return 0;
}
[解决办法]
话说这个还真不好找。不过总算找到了。问题出在Merge和MSort分别进行了一次从a到b的复制。
举个例子，现在a 是 3 2 1
那么一次之后
b 是 2 3 ，1
按道理进行Merge之后应该是1（第三个元素放在第一个），2（第一个元素放在第二个位置），3（第二个元素放在最后一个。但是Merge又从a拷贝了一次，自然就是1（第三个元素），3（第一个元素），2（第二个元素）
