ch8_9.txt
上传用户:lgb298
上传日期:2013-03-22
资源大小:1025k
文件大小:1k
- void mergesort(JD r[],int n)
- { int i,s=1;
- JD t[M];
- while(s<n)
- { tgb(s,n,r,t);
- s*=2;
- if(s<n) { tgb(s,n,t,r); s*=2; }
- else { i=1;
- while(i<=n) r[i]=t[i++];
- }
- }
- }
- /*趟归并,s为有序子表长度*/
- void tgb(int s,int n,JD r[],JD t[])
- { int i=1;
- while(i<=(n-2*s+1))
- { merge(r,i,i+s-1,i+2*s-1,t);
- i=i+2*s;
- }
- if(i<(n-s+1)) merge(r,i,i+s-1,n,t);
- else
- while(i<=n) t[i]=r[i++];
- }
- /* 合并首尾相接的两个有序子表(h,m)和(m+1,w)*/
- void merge(JD r[],int h,int m,int w,JD t[])
- { int i,j,k;
- i=h; j=m+1; k=h-1;
- while((i<=m)&&(j<=w))
- { k++;
- if(r[i].key<=r[j].key)
- t[k]=r[i++];
- else
- t[k]=r[j++];
- }
- if(i>m)
- while(j<=w) t[++k]=r[j++];
- else
- while(i<=m) t[++k]=r[i++];
- }