第8章排序 8.3 树型选择排序《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

8.1 概述 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 第8章 内部排序 树型选择排序 13 49 38 38 38 65 65 97 76 13 13 13 27 27 49 49 38 65 97 76 13 27 49 27 49 38 38 38 65 65 97 76 * 27 76 27 27 49 堆排序 1．堆的定义 若有n个元素(a1，a2，a3，…，an)，当满足如下条件： ai≤a2i ai≥a2i （1） ai≤a2i+1 或 (2) ai≥a2i+1 其中i=1,2,…,n/2  则称此n个元素a1，a2，a3，…，an为一个堆。 若将此元素序列按顺序组成一棵完全二叉树，则（1）称为小根堆（二叉树的所有根结点值小于或等于左右孩子的值），（2）称为大根堆（二叉树的所有根结点值大于或等于左右孩子的值）。 小根堆 8 16 9 1 6 2 11 10 5 4 大根堆 16 9 8 10 6 2 11 1 5 4 1 6 8 12 9 16 2 11 5 14 1 9 8 10 6 16 2 11 5 4 不是堆 不是堆 2.堆与完全二叉树关系 若n个元素a1，a2，a3，…，an满足堆，且让结点按1、2、3、…、n顺序编号，根据完全二叉树的性质（若i为根结点，则左孩子为2i，右孩子为2i+1）可知，一个堆对应着一颗完全二叉树，堆排序实际与一棵完全二叉树有关。若将元素初始序列组成一棵完全二叉树，则堆排序可以包含建立初始堆（使排序码变成能符合堆的定义的完全二叉树）和利用堆进行排序两个阶段。 3、实例 如序列(80,75,40,62,73,35,28,50,38,25,47,15)可以验证它满足堆的条件,因此是一个堆.下图给出其对应的完全二叉树. 1 80 75 40 62 73 28 35 50 38 25 47 15 3 2 4 5 6 7 8 9 10 11 12 堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫~ 堆排序需解决的两个问题： 如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 第二个问题解决方法——筛选 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选” 例 13 27 38 49 65 76 50 97 97 27 38 49 65 76 50 13 输出：13 27 49 38 97 65 76 50 13 输出：13 97 49 38 27 65 76 50 13 输出：13 27 38 49 50 27 65 76 97 13 输出：13 27 65 49 50 27 38 76 97 13 输出：13 27 38 49 65 50 27 38 76 97 13 输出：13 27 38 76 65 50 27 38 49 97 13 输出：13 27 38 49 50 65 76 27 38 49 97 13 输出：13 27 38 49 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 97 76 27 38 49 50 13 输出：13 27 38 49 50 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 76 65 97 27 38 49 50 13 输出：13 27 38 49 50 65 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 76 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 76 97 堆排序的演示 typedef SqList HeapType; 1 9 8 10 6 16 2 11 4 5 H.length 10 H.r 1 2