合并排序 - 编程论坛

#2

zhu2240392012-10-16 23:17

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

#3

zhu2240392012-10-16 23:20

}
    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++?
    }

#4

zhu2240392012-10-16 23:22

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

#5

zhu2240392012-10-16 23:30

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.合并过程
这两个过程是在一个递归式里面进行的

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

#6

zhu2240392012-10-16 23:32

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

#7

zhu2240392012-10-16 23:34

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

#8

寒风中的细雨2012-10-16 23:37

回复 7楼 zhu224039

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

#9

Silence_2012-10-17 00:54

回复 2楼 zhu224039

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++];
你说的那段代码是没问题的，错误主要是以上红色地方，去掉就行了.

#10

Silence_2012-10-17 01:00

回复 6楼 zhu224039

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

#11

Silence_2012-10-17 01:02

回复 3楼 zhu224039

是这i++ j++的问题，去掉后就没问题了.

#12

zhu2240392012-10-17 02:33

你说的是那里

#13

zhu2240392012-10-17 02:35

算法介绍之分治算法
#include
void combin(int num[],int r,int p,int q)  /*合并过程*/
{
    int lift[q-p],right[r-q+1],i,j,k;
    for(i=0;i<Q-P;I++){
        lift[i]=num[p+i];
    }
    for(i=0;i<R-Q+1;I++){
        right[i]=num[q+i];
    }
    i=0;j=0;
    for(k=p;k<=r;k++){
     if(i<Q-P&&J<R-Q+1){
        if(lift[i]>right[j]){
            num[k]=right[j];
            j++;
        }
        else{
            num[k]=lift[i];
            i++;
        }
      }
    else if(i==q-p){
          num[k]=right[j];
          j++;
      }
      else if(j==r-q+1){
          num[k]=lift[i];
          i++;
      }
      }
}
void combin_sort(int num[],int n,int p )   ;----------------递归分解合并过程
{
       int q;
       q=(n+p)/2;
       if(p<N){
        combin_sort(num,q,p);
        combin_sort(num,n,q+1);
        combin(num,n,p,q+1);
    }

}
int main(int argc, char *argv[])               /*对一串无序的数据进行排序 */
{
    int num[20],i=0,j;
    printf("please insert num insert q to quit\n");
    while(scanf("%d",num+i)==1){
        i++;
    }
    if(i>1){
      combin_sort(num,i-1,0);
    }
    for(j=0;j<I;J++)
    printf("%d ",num[j]);
    printf("done\n");
    return 0;
}

分治的中心思想为
满足条件 1个问题可以被分解成N个相同问题。
求解过程由N个问题经过组合而得到要求解的问题。
分治包含操作过程
1.分解过程 2.合并过程
分解过程是一个典型的递归思想
既然是递归那么就应该有递归函数（函数完成动作部分），递归终止条件（原子操作），靠近递归终止条件的表达式

分治算法的递归函数式  x={a1,a2..........an} 代表问题集合  用F(1,N) （n>=1）将其1分为二就得到集合 f(1,n/2)和f(n/2+1,n)
f(1,n)=f(1,n/2) combin f(n/2+1,n)
然后对 f(1,n/2)和 f(n/2+1,n) 进行一分为二
归纳出
F(x,y)=f(x,y/2) combin f(y/2+1,y)   f(x,y/2)  表示的是集合{x.......y/2}  f(y/2+1,y) 表示的集合{y/2+1..............y}
当x，y的值  是有上一个（a,b）给出的如果f(x,y)是左边部分那么有表达式  x=a y=(a+b)/2 如果是右半部分就会是x=(a+b)/2+1,y=b
这么个关系存在 y的取值是上一个a,b的中间。
原子操作部分的确定
那么原子操作怎么来确定对f(x,y)不能再分解条件 (x+y)/2=x和(x+y)/2=y 成立  注意这个/ 是取商运算，在整数运算，
如果余数是0 可以演化出x=y的  所以得到原子操作的判断条件是 x=y
因为x<=y的，所以只要x<Y就要进行递归分解

递归靠近条件表达式就是  取中间量表达式  x+y/2

完成动作部分就是合并过程  那么合并怎么来实现
合并规则
在上面排序程序是将两个排好序的数组进行合并  F(a,(a+b)/2)和F（(a+b)/2+1,b）两个数组集合元素进行插入插入排序u 得到 F(a,b)

个人浅见希望对大家有用

#14

zhu2240392012-10-17 02:36

#include <stdio.h>
void combin(int num[],int r,int p,int q)
{
    int lift[q-p],right[r-q+1],i,j,k;
    for(i=0;i<q-p;i++){
        lift[i]=num[p+i];
    }
    for(i=0;i<r-q+1;i++){
        right[i]=num[q+i];
    }
    i=0;j=0;
    for(k=p;k<=r;k++){
     if(i<q-p&&j<r-q+1){
        if(lift[i]>right[j]){
            num[k]=right[j];
            j++;
        }
        else{
            num[k]=lift[i];
            i++;
        }
      }
    else if(i==q-p){
          num[k]=right[j];
          j++;
      }
      else if(j==r-q+1){
          num[k]=lift[i];
          i++;
      }
      }
}
void combin_sort(int num[],int n,int p )
{
       int q;
       q=(n+p)/2;
       if(p<n){
        combin_sort(num,q,p);
        combin_sort(num,n,q+1);
        combin(num,n,p,q+1);
    }

}
int main(int argc, char *argv[])
{
    int num[20],i=0,j;
    printf("please insert num insert q to quit\n");
    while(scanf("%d",num+i)==1){
        i++;
    }
    if(i>1){
      combin_sort(num,i-1,0);
    }
    for(j=0;j<i;j++)
    printf("%d ",num[j]);
    printf("done\n");
    return 0;
}

这个是编译成功的分治排序算法

#15

zhu2240392012-10-17 02:38

哦，程序运行正确么
我用递归做的，对于不用递归的实现没弄过

#16

zhu2240392012-10-17 02:54

奇偶情况下都是正确的么程序运行的结果