堆排序--大顶堆排序(数据结构 严蔚敏).doc

《堆排序--大顶堆排序(数据结构 严蔚敏).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、大顶堆排序#include"stdio.h"#include"stdlib.h"//*****************************************typedefintKeyType;intn=0;typedefstruct{//定义记录类型KeyTypekey;//关键字项}RedType;typedefstruct{RedTyper[21];//r[0]闲置或用作哨兵单元intlength;//顺序表长度}Sqlist,*Head;//顺序表类型//*****************************************//调整函数void

2、HeapAdjust(Sqlist&H,ints,intm){intj;RedTyperc;rc=H.r[s];for(j=2*s;j<=m;j*=2){if(j=H.r[j].key)break;H.r[s]=H.r[j];s=j;}H.r[s]=rc;//插入}//HeapAdjust//*****************************************//排序输出函数voidHeapSort(Sqlist&H){inti;printf("请输入要排序的数的的个数(20

3、以内):");//建立堆scanf("%d",&n);printf("请输入这%d个数（用空格隔开）:",n);H.length=n;for(i=1;i<=n;i++)scanf("%d",&H.r[i].key);RedTypetemp;for(i=H.length/2;i>0;--i)HeapAdjust(H,i,H.length);for(i=H.length;i>1;--i){temp=H.r[i];H.r[i]=H.r[1];H.r[1]=temp;HeapAdjust(H,1,i-1);}printf("大顶堆排序结果如下:");//输出堆

4、for(i=1;i<=n;i++)printf("%d",H.r[i].key);}//HeapSort//*****************************************//主函数voidmain(){SqlistH;HeapSort(H);//堆排序printf("");}运行结果如下：