分治法排序

发布网友发布时间：2022-04-26 07:58

共2个回答

热心网友时间：2022-06-25 13:53

你写的太乱了。不完全是他说的漏掉数据问题。而是边界完全有问题，导致了数组内的数据都变成错误的了。看得有点乱。整了个比较规范的给你参考参考。
void merge(int a[] , int temp[] , int Lpos , int Rpos , int RightEnd)
{
int i , LeftEnd , num , tmppos;

LeftEnd = Rpos - 1;
tmppos = Lpos;
num = RightEnd - Lpos + 1;
while (Lpos <= LeftEnd && Rpos <= RightEnd)
if (a[Lpos] <= a[Rpos]) temp[tmppos ++] = a[Lpos ++];
else temp[tmppos ++] = a[Rpos ++];
while (Lpos <= LeftEnd) temp[tmppos ++] = a[Lpos ++];
while (Rpos <= RightEnd) temp[tmppos ++] = a[Rpos ++];
for (i = 0; i < num; i ++)
{
a[RightEnd] = temp[RightEnd];
RightEnd --;
}
}

void msort(int a[] , int temp[] , int L , int r)
{
int c;

if (L < r)
{
c = (L + r) / 2;
msort(a , temp , L , c);
msort(a , temp , c + 1 , r);
merge(a , temp , L , c + 1 , r);
}
}

void mergesort(int a[] , int n) //调用此函数，a为排序数组，n为数组个数
{
int temp[MAXN];//MAXN表示题目中可能出现的最大数组上限

msort(a , temp , 0 , n - 1);
}

热心网友时间：2022-06-25 13:54

问题之处：
1．数组要传递引用，否则不会被改变。
2．代码要加括号：
for(int k=p-1;k!=r;++k) {
if(L[i]<=R[j]){
A[k]=L[i];
++i;
}
else if(L[i]>R[j]){
A[k]=R[j];
++j;
}
}
－－－－－－－－－－－－－－－－－－－
完整代码：
#include<iostream>
#include<vector>
#include<cstdlib>

using namespace std;

void MERGE(vector<int> &A,int p,int q,int r)
{
int i,j,k=0;
int n1=q-p+1;
int n2=r-q;
vector<int> L((n1+1),0),R((n2+1),0);
for(vector<int>::size_type i=0;i!=n1;++i)
L[i]=A[p+i-1];
for(vector<int>::size_type j=0;j!=n2;++j)
R[j]=A[q+j];
L[n1]=88888;
R[n2]=88888;

i=0;
j=0;
for(int k=p-1;k!=r;++k) {
if(L[i]<=R[j]){
A[k]=L[i];
++i;
}
else if(L[i]>R[j]){
A[k]=R[j];
++j;
}
}
}
void MERGE_SORT(vector<int> &A,int p,int r)
{
int q;
if(p<r){
if((r-p+1) % 2==0)q=(r+p+1)/2-1;
if((r-p+1) % 2==1)q=(r+p)/2;
MERGE_SORT(A,p,q);
MERGE_SORT(A,q+1,r);
MERGE(A,p,q,r);
}
}
int main()
{
int val;
vector<int> A;
//while(cin>>val)
// A.push_back(val);
A.push_back(9);
A.push_back(8);
A.push_back(2);
A.push_back(4);
A.push_back(3);
MERGE_SORT(A,1,A.size());
for(vector<int>::iterator ix=A.begin();ix!=A.end();++ix)
cout<<*ix<<' ';
system("pause");
return 0;
}