ch8_9.txt
上传用户:lgb298
上传日期:2013-03-22
资源大小:1025k
文件大小:1k
源码类别:

软件工程

开发平台:

C/C++

  1. void mergesort(JD r[],int n)
  2. {  int i,s=1;
  3.    JD t[M];
  4.    while(s<n)
  5.    {  tgb(s,n,r,t);
  6.       s*=2;
  7.       if(s<n) { tgb(s,n,t,r); s*=2; }
  8.       else  {  i=1;
  9.                while(i<=n)  r[i]=t[i++];
  10.             }
  11.    }
  12. }
  13. /*趟归并,s为有序子表长度*/
  14. void tgb(int s,int n,JD r[],JD t[])
  15. {  int i=1;
  16.    while(i<=(n-2*s+1))
  17.    {  merge(r,i,i+s-1,i+2*s-1,t);
  18.       i=i+2*s;
  19.    }
  20.    if(i<(n-s+1))  merge(r,i,i+s-1,n,t);
  21.    else   
  22.       while(i<=n)  t[i]=r[i++];
  23. }
  24. /* 合并首尾相接的两个有序子表(h,m)和(m+1,w)*/
  25. void merge(JD r[],int h,int m,int w,JD t[])
  26. {  int i,j,k;
  27.    i=h; j=m+1; k=h-1;
  28.    while((i<=m)&&(j<=w))
  29.    {  k++;
  30.       if(r[i].key<=r[j].key)
  31.          t[k]=r[i++];
  32.       else
  33.          t[k]=r[j++];
  34.    }
  35.    if(i>m)
  36.       while(j<=w)  t[++k]=r[j++];
  37.    else
  38.       while(i<=m)  t[++k]=r[i++];
  39. }