基于堆的排序.doc_第1页
基于堆的排序.doc_第2页
基于堆的排序.doc_第3页
基于堆的排序.doc_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

四、基于堆的排序输入：数组A，数组的元素个数n输出：按递增顺序排序的数组A1.template 2.void heap_sort(Type A,int n)3.4.int i;5.make_heap(A,n);建立一个最大堆6.for(i=n;i1;i-)7.swap(A1,Ai);swap(A1,Ai)实现的功能：将最大堆的第1个元素（即最上面的元素）放在数组中的最后1个元素的位置上8.sift_down(A,i-1,1);将最大堆中剩下的元素再重新排序，形成新的最大堆和新的数组（新的堆和数组不包括已经排好序的元素），然后转到第7行继续循环执行swap(A1,Ai)语句，直到所构成的新堆的元素个数减少到1为止9.10.基于堆的函数中用到的子函数sift_down()，功能是完成元素下移操作。其算法如下：输入：数组H，数组的元素个数n,被下移的元素下标i输出：维持堆的性质的数组H设被下移的元素为I1.template 2.void sift_down(Type H,int n,int i)3.4.BOOL done=FALSE;5.if(2*i)=n)判断被下移的元素I是否有儿子while(!done & (i=2*i)=n)经过i=2*i赋值后，被下移的元素I的序号变成2i了if(i+1Hi)此时的i+1表示被下移的元素I的右儿子，i+1Hi用来判断左右儿子的大小i=i+1;i表示左儿子的序号，i+1表示右儿子的序号，则如果满足Hi+1Hi条件，则表明右儿子比左二子大，则i=i+1表示接下来要与被下移的元素I进行比较大小的元素变成了右儿子，实现的功能就是将左右儿子互换if(Hi/2Hi)Hi/2表示左二子，Hi表示被下移的元素IHi/2Hi用来判断被下移元素I和左二子的大小swap(Hi/2,Hi);将被下移的元素I与左儿子互换else done=TRUE;基于堆的函数中用到的子函数make_heap()，功能是建造一个堆。其算法如下：输入：数组A，数组的元素个数n输出：n个元素的堆A1.template 2.void make_heap(Type A,int n)3.4.int i;5.An=A0;因为数组是从第0号元素开始存放数据，而堆是从数组的第1号元素开始存放数据，则An=A0就是建立一个结构被打乱的堆。6.for(i=n/2;i=1;i-)7.sift_down(A,n,i);实现下移操作，对对堆进行整理。8.第5行的make_heap算法的执行时间是（n）；sift_down每执行一次花费的时间为O(log2n)
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论