用分治法排序，大家看看出什么有关问题了

2013-07-09

用分治法排序，大家看看出什么问题了。小弟新手，对递归掌握的不是很好，这是看书把伪代码翻译过来的，麻烦大神

用分治法排序，大家看看出什么问题了。
小弟新手，对递归掌握的不是很好，这是看书把伪代码翻译过来的，麻烦大神们看看哪里出问题了。

#include<stdio.h>
void MERGE(int *A,int p,int q,int r);
void MERGE_SORT(int *A,int p,int r);

int main()
{
int a[5]={1,5,7,8,4};
int i;
MERGE_SORT(a,0,4);
for(i=0;i<5;i++)
{
printf("%d ",a[i]);
}
return 0;
}

void MERGE(int *A,int p,int q,int r)
{
int L[3],R[3];
int i,j,k;
for(i=0;i<=r;i++)
{
if(i<=q)
L[i]=A[i];
else
R[i-q-1]=A[i];
}
if((r/2)*2!=r)
{
j=(r-1)/2;
k=(r-1)/2;
}
else
{
j=r/2;
k=(r-1)/2;
}
for(i=r;i>=0;i--)
{
if(L[j]>=R[k])
{
A[i]=L[j];
j-=1;
}
else
{
A[i]=R[k];
k-=1;
}
}
//printf("%d,%d\n",L[0],L[1]);
//printf("%d,%d\n",R[0],R[1]);
}

void MERGE_SORT(int *A,int p,int r)
{
int q;
if(p<r)
{
q=r/2;
MERGE_SORT(A,p,q);
MERGE_SORT(A,q+1,r);
MERGE(A,p,q,r);
}
if(p>=r)
MERGE(A,p,q,r);
}

问题应该是出在函数void MERGE_SORT(int *A,int p,int r)的递归中，求解答啊！！！递归 C
[解决办法]
你那个合并数组有点问题，还有就是用c感觉会造成段错误，c++可以用，不知道理解对不对你暂且看看吧

#include<iostream.h>
void MERGE(int *A,int p,int q,int r,int m);
void MERGE_SORT(int *A,int p,int r);
int main()
{
int i = 0;
int a[5]={1,5,7,8,4};
     MERGE_SORT(a,0,4);
for(;i<5;i++)
cout<<a[i]<<endl;
return 0;
}

void MERGE(int *A,int p,int q,int r,int m){
int i,j,k;
int *b = new int[m];
i = p;
j = q+1;
k = 0;
while(i<=q&&j<=r)
{
if(A[i]>A[j])
{
b[k++] = A[j++];
}
else
b[k++] = A[i++];

}
if(i==q+1)
{
      for(;j<=r;j++)
  b[k++] = A[j];
}
else
{
for(;i<=q;i++)
{
b[k++] = A[i];

}
}
k=0;
for(i=p;i<r+1;i++)
A[i]=b[k++];
delete b ;

}

void MERGE_SORT(int *A,int p,int n){
if(p<n){
int q;
q=(n+p)/2;
MERGE_SORT(A,p,q);
MERGE_SORT(A,q+1,n);
MERGE(A,p,q,n,n-p+1);

}


}

[解决办法]
可以参考下我的这篇博文http://blog.csdn.net/xuchao1229/article/details/8167689
[解决办法]
int q;
    if(p<r)
    {
        q=r/2;
        MERGE_SORT(A,p,q);

        MERGE_SORT(A,q+1,r);
        MERGE(A,p,q,r);
    }
    if(p>=r)
        MERGE(A,p,q,r);

如果进入第二个循环，那么q就是未定义的，你让编译器怎么merge

热点排行

C语言

用分治法排序，大家看看出什么有关问题了