//这个程序本来是合并排序的，但是输出的结果与预期的不符，哪位大神能够解释一下
#include <iostream.h>
#include <memory.h>

void merge(int A[],int p,int q,int r,int m);
void merge_sort(int A[],int n);

int main()
{
    int B[]={12,5,4,63,79,33,10,58,69,14};
    merge_sort(B,10);
    for(int i=0;i<10;i++)
        cout<<B[i]<<" ";
    cout<<endl;
    return 0;
}
void merge(int A[],int p,int q,int r)
{
    int* bp = new int[r-p+1];
    int i,j,k;
    i=p;
    j=q+1;
    k=0;
    while(i<=q&&j<=r)
    {
        if(A[i]<=A[j])
            bp[k++] = A[i++];
        else
            bp[k++] = A[j++];
    }
    if(i==q+1)
    {
        for(;j<=r;j++)
            bp[k++] = A[j++];
    }
    else
    {
        for(;i<=q;i++)
            bp[k++] = A[i++];
    }
    k=0;
    for(i=p;i<=r;i++)
        A[i++] = bp[k++];
    //cout<<A[i]<<endl;
    delete bp;
}
void merge_sort(int A[],int n)
{
    int s,i,t=1;
    while(t<n)
    {
        s=t; 
        t = 2*s; 
        i=0;   //s是合并前序列的大小，t是合并后序列的大小，每次合并元素的起始位置为i
        while(i+t<n)
        {   
            merge(A,i,i+s-1,i+t-1);
            i=i+t;
        }
        if(i+s<n)
            merge(A,i,i+s-1,n-1);
    }   
}

while(i<=q&&j<=r)
    {
        if(A[i]<=A[j])
            bp[k++] = A[i++];
        else
            bp[k++] = A[j++];
    }

这段代码 我不知道你的机器是 先K+1再 bp[k] 还是先bp[k]然后 k+1
这个是疑问1

}
    if(i==q+1)
    {
        for(;j<=r;j++)
            bp[k++] = A[j++];   -------------》这个位置A[J++]改成 A[J]
     }
    else
    {
        for(;i<=q;i++)
            bp[k++] = A[i++]; -----------------》还有这个地方  自己想想for里面是不是在进行i++ 或者j++?
    }

for(i=p;i<=r;i++)
        A[i++] = bp[k++];     ------------->这个地方也请兄弟自己修改
    //cout<<A[i]<<endl;
    delete bp;

void merge_sort(int A[],int n)
{
    int s,i,t=1;
    while(t<n)
    {
        s=t;
        t = 2*s;
        i=0;   //s是合并前序列的大小，t是合并后序列的大小，每次合并元素的起始位置为i
        while(i+t<n)
        {   
            merge(A,i,i+s-1,i+t-1);
            i=i+t;
        }
        if(i+s<n)
            merge(A,i,i+s-1,n-1);
    }   
}

这段代码 还请兄台自己再琢磨下

我不会C++ 但是我感觉你这个地方很混乱  在while 循环中  我看不到分解 的过程
倒是看到的是 两个已经排好序的数据集合的 合并过程 但是你的main 函数里面给出的 是一个数据很混乱的数据集合  

这个算法的精华
1.分解过程
2.合并过程
这两个过程 是在一个递归式里面进行的


我对此算法有过描述  
有兴趣可以去看看

收到的鲜花

• Silence_ 于 2012-10-17 01:04 送鲜花  5朵   附言：我很赞同

我不懂C++
但是觉得 兄台还是亲自再查阅下书籍的好 。最起码在概念上 理解透彻后再进行代码实现

这个怎么从数据结构区  到了 C++区呢？

最初是c++版的帖   我把它转到了数据结构版了  

if(i==q+1)
    {
        for(;j<=r;j++)
            bp[k++] = A[j++];
    }
    else
    {
        for(;i<=q;i++)
            bp[k++] = A[i++];
    }
    k=0;
    for(i=p;i<=r;i++)
        A[i++] = bp[k++];
你说的那段代码是没问题的，错误主要是以上红色地方，去掉就行了.

兄台，这这个上面还没有用到分治，只有有一个合并的过程，没用递归和分治的策略去解决这个问题。