heap_sort.cpp

这是本人精心搜集的关于常用图论算法的一套源码

#include "sqlist.h"                  
void insert_heap(recordfile r,int l,int u)       //实现"筛选"的算法
/*  r[l]~r[u] 是一棵完全二叉树，以 r[l +1] 和 r[l +2] 为根的左右子树已经是堆，
   本算法调整 r[l]，使整个序列 r[l]~r[u]成为一个堆   */
{ int i,j;
  i=l;  j=2*l;  r[0]=r[l];
  while(j<=u){ if(j<u&&r[j].key>r[j+1].key) j++;  // 令j指向左右孩子中较小的孩子
               if(r[0].key>r[j].key){ r[i]=r[j]; i=j; j*=2; }
                else break;            //  跳出循环
             } //end_while
  r[i]=r[0];
}

 void heapsort (recordfile r,int n)    //堆排序
 { int i;  record t;
   for (i= n/2; i>0; i--) sift (r,i,n);
   for (i=n;i>1;i--) { t=r[1]; r[1]=r[i]; r[i]=t; insert_heap(r,1,i-1); }
 }

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
void main(void)
{
  int i;  time_t t;
  recordfile r;
  srand((unsigned)time(&t));
  for(i=1;i<=20; i++) r[i].key=rand() % 100;
  printf(" origil array is\n");
  for(i=1;i<=20; i++) printf("%4d",r[i].key);
  heapsort(r,20);
  printf("\n sort array is\n");
  for(i=1;i<=20; i++) printf("%4d",r[i].key);
}