《数据结构与算法设计PPT (47).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (47).pdf（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第9章 排序9.6 堆排序2021/2/241 锦标赛排序方法对比简单选择排序算法减少了许多排序时间，但是使用了较多的附加存储。如果有n 个对象，必须使用至少 2n-1 个结点来存放胜者树。最多需要找到满足 2k-1 n 2k 的k，使用 2*2k-1 个结点。每个结点包括关键码、对象序号和比较标志三种信息。锦标赛排序算法性能分析堆排序(Heap Sort)利用堆数据结构，即可以利用树形结构存储比较结果的历史，还可以减少算法的辅助存储空间的数量 堆排序分为两个步骤：第一步，根据初始输入数据，利用堆的调整算法FilterDown()形成初始堆第二步，通过一系列的对象交换和重新调整堆进行排序。21
2、2525*491608012345i212525*164908025431i21 25 49 25*16 08初始关键码集合21 25 49 25*16 08i=2 时的局部调整建立初始大根堆过程212525*491608012345i492525*16210802543121 25 49 25*16 0849 25 21 25*16 08i=0 时的局部调整形成最大堆i=1 时的局部调整建立初始大根堆过程大根堆的向下调整算法template voidMaxHeap:FilterDown(const inti,const intEndOfHeap)intcurrent=i;intchild=2
3、*i+1;Typetemp=heapi;while(child=EndOfHeap)if(child+1 EndOfHeap&heapchild.getKey()=heapchild.getKey()break;else heapcurrent=heapchild;current=child;child=2*child+1;heapcurrent=temp;大根堆的向下调整算法（1）将数组中存储的元素转换成初始大根堆for(inti=(CurrentSize-2)/2;i=0;i-)FilterDown(i,CurrentSize-1);（2）利用初始的大根队进行排序堆排序的算法思想 最大堆的
4、第一个对象V0具有最大的关键码，将V0与Vn对调，把具有最大关键码的对象交换到最后 再对前面的n-1个对象，使用堆的调整算法FilterDown(0,n-1)，重新建立最大堆。结果具有次最大关键码的对象又上浮到堆顶，即V0位置。再对调V0和Vn-1，调用FilterDown(0,n-2)，对前n-2个对象重新调整，。如此反复执行，最后得到全部排序好的对象序列。利用初始的大根堆排序的思想492525*211608012345082525*16214902543149 25 21 25*16 0808 25 21 25*16 49交换 0 号与 5 号对象,5 号对象就位初始最大堆大根堆排序的过程
5、2021/2/24112525*082116490123451625*0825214902543125 25*21 08 16 4916 25*21 08 25 49交换 0 号与 4 号对象,4 号对象就位从 0 号到 4 号 重新调整为最大堆2021/2/241225*1608212549012345081625*25214902543125*16 21 08 25 4908 16 21 25*25 49交换 0 号与 3 号对象,3 号对象就位从 0 号到 3 号 重新调整为最大堆2021/2/2413211625*082549012345081625*25214902543121 16
6、 08 25*25 4908 16 21 25*25 49交换 0 号与 2 号对象,2 号对象就位从 0 号到 2 号 重新调整为最大堆2021/2/2414160825*212549012345081625*25214902543116 08 21 25*25 4908 16 21 25*25 49交换 0 号与 1 号对象,1 号对象就位从 0 号到 1 号 重新调整为最大堆2021/2/2415template voidMaxHeap:HeapSort()/对表heap0到heapn-1进行排序,使得表中各/个对象按其关键码非递减有序。for(inti=(CurrentSize-2)/
7、2;i=0;i-)FilterDown(i,CurrentSize-1);/初始堆for(i=CurrentSize-1;i=1;i-)Swap(heap0,heapi);/交换FilterDown(0,i-1);/重建最大堆 堆排序算法的实现堆排序算法性能分析 若设堆中有n 个结点，且 2k-1n 2k，则对应的完全二叉树有k 层。在第i层上的结点数 2i (i=0,1,k-1)。在第一个形成初始堆的for循环中对每一个非叶结点调用了一次堆调整算法FilterDown()，因此该循环所用的计算时间为：其中，i是层序号，2i 是第i层的最大结点数，(k-i-1)是第i层结点能够移动的最大距离。()-=-2022kiiik,在第二个for循环中，调用了n-1次FilterDown()算法，该循环的计算时间为O(nlog2n)。因此，堆排序的时间复杂性为O(nlog2n)。算法的空间复杂性为O(1)。堆排序是一个不稳定的排序方法。njnjjikkjkjjjkkjjkkii/=-=-=-=-=11111111202222222122)(