归并排序.txt

数据结构用C语言实现的各种排序方法

void mergesort(JD r[],int n)//r[]为要排序的数组
{  int i,s=1; //s为每次分组的区间值
   JD t[M]; //数组t[]为引入的辅助空间
   while(s<n)
   {  tgb(s,n,r,t);
      s*=2;
      if(s<n) { tgb(s,n,r,t); s*=2; }
      else  {  i=1;
               while(i<=n)  r[i]=t[i++]; 
            }//else表示排序结束，将已排好序的辅助数组t重新置回r中
   }
}

void tgb(int s,int n,JD r[],JD t[])
{  int i=1;
   while(i<=(n-2*s+1))// 相当于i+2*S－1<=n，即本组的最后一个元素要<=n
                      //其中i+2*S表示下一组第一个元素
   {  merge(r,i,i+s-1,i+2*s-1,t);//进行一次分组后调用归并函数merge
      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++];//若剩余元素的区间减半后，将仍不够分组长度的元素直接放入数组t中
}

void merge(JD r[],int h,int m,int w,JD t[])//将数组r[h...m]与r[m+1...w]正序归并到数组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)  //将剩余数值全部赋给t
      while(j<=w)  t[++k]=r[j++];
   else
      while(i<=m)  t[++k]=r[i++];
}