5.6排序算法--堆排序与对分查找 课件-2021-2022学年浙教版（2019）高中信息技术选修1

第五章 数据结构与算法 选修1《数据与数据结构》 5.6 排序算法 --堆与对分查找 学习目标 排序算法 堆排序算法 顺序查找算法 对分查找算法 堆排序算法 堆是一种数据结构，满足以下性质： 1、堆是一种完全二叉树 2、子结点的值总是小于（或者大于）它的父节点 ·堆的概念 排序算法 99 40 30 39 2 9 28 29 15 最大堆：每个节点的值都大于或等于其孩子节点的值 最小堆：每个节点的值都小于或等于其孩子节点的值 如右图，就是一个最大堆。 堆排序算法 排序算法 ·堆的存储结构 堆可以用数组来存储。 99 40 30 39 2 15 9 28 29 0 1 2 3 4 5 6 7 8 9 99 40 30 39 2 9 28 29 15 0 1 3 7 2 6 4 5 8 数组a： 根节点 树第二层 树第三层 树第四层 堆排序算法 堆排序算法是将待排序序列构造成一个最大堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个最大堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。 ·堆排序的基本思路 对长度为 n 的数组而言，堆排序的时间复杂度为 O(nlogn)。 排序算法 ·堆排序的效率 堆排序算法 ·图解堆排序算法(升序) 排序算法 在学习堆排序之前，需了解树的一些知识点。 例如：列表a=[ 40, 38, 65, 97, 76, 13, 27, 49，10, 7]，列表如果是以数组的形式存储，则如下图。若以树的结构来存储，则如右图。 那么对于节点R[ i ]（i是列表的索引号）而言： (1)它的左孩子结点是：R[ 2*i+1 ] (2)它的右孩子结点是：R[ 2*i+2 ] (3)它的父结点是：R[ (i-1)//2 ] (4)最大堆满足：R[ i ] >= R[ 2*i+1 ] 且 R[ i ] >= R[ 2i+2 ] 40 38 65 97 76 27 49 10 13 7 0 1 3 7 2 6 4 5