ch8_7.c

数据结构的一些小算法

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

void sift(JD r[],int k,int m)
{  int i,j;
   JD x;
   i=k;  x=r[i]; j=2*i;
   while(j<=m)
   {  if((j<m)&&(r[j].key>r[j+1].key))  j++;
      if(x.key>r[j].key)
      {  r[i]=r[j];
         i=j;
         j*=2;
      }
      else   j=m+1;
   }
   r[i]=x;
}

void heapsort(JD r[],int n)
{  int i;
   JD x;
   for(i=n/2;i>=1;i--)
      sift(r,i,n);
   for(i=n;i>=2;i--)
   {  x=r[1];
      r[1]=r[i];
      r[i]=x;
      sift(r,1,i-1);
   }
}

void main()
{
    static JD r[]={0,49,38,65,97,76,13,27,50};
    int i,n=8;
    heapsort(r,n);
    for(i=n;i>=1;i--)
      printf("%d  ",r[i].key);
    printf("\n");
}