排序程序

/* algo10-9.c 堆排序 */

#include

typedef int InfoType; /* 定义其它数据项的类型 */ #include\ #include\

typedef SqList HeapType; /* 堆采用顺序表存储表示 */ void HeapAdjust(HeapType *H,int s,int m) /* 算法10.10 */

{ /* 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数 */

/* 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言) */

RedType rc; int j;

rc=(*H).r[s];

for(j=2*s;j<=m;j*=2)

{ /* 沿key较大的孩子结点向下筛选 */

if(j

break; /* rc应插入在位置s上 */ (*H).r[s]=(*H).r[j]; s=j; }

(*H).r[s]=rc; /* 插入 */ }

void HeapSort(HeapType *H)

{ /* 对顺序表H进行堆排序。算法10.11 */ RedType t; int i;

for(i=(*H).length/2;i>0;--i) /* 把H.r[1..H.length]建成大顶堆 */ HeapAdjust(H,i,(*H).length); for(i=(*H).length;i>1;--i)

{ /* 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换 */ t=(*H).r[1];

(*H).r[1]=(*H).r[i]; (*H).r[i]=t;

HeapAdjust(H,1,i-1); /* 将H.r[1..i-1]重新调整为大顶堆 */

}

}

void print(HeapType H) {

int i;

for(i=1;i<=H.length;i++)

printf(\ printf(\ }

#define N 8 void main() {

RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}}; HeapType h; int i;

for(i=0;i

HeapSort(&h);

printf(\排序后:\\n\ print(h); }