ch8_9.c

来自「一个很好的数据结构（C语言版）讲义。附带全部所需算法源码。」· C语言 代码 · 共 56 行

#include <stdio.h>
#define M 15
typedef struct
{  int key;
  /* float info;*/
}JD;

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++];
}

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++];
}

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++];
	    }
   }
}

void main()
{
    static JD r[]={0,49,38,65,97,76,13,27};
    int i,n=7;
    mergesort(r,n);
    for(i=1;i<=n;i++)
      printf("%d  ",r[i].key);
    printf("\n");
}