数据结构 第十章 内排序.ppt

第十章 排序 10.1 插入排序 1、直接插入排序 2、其它插入排序 算法描述 10.2 快速排序 算法描述与分析 10.3 选择排序 3、堆排序 10.4 归并排序 10.5 基数排序 （3）堆排序：若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则可得到n个元素的次小值；如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。 实现堆排序需解决的两个问题 如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 二个问题解决方法——筛选 3、堆排序 （4）筛选 方法： 输出堆顶元素之后，以堆中最后一个元素替代之； 然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换； 重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选” 3、堆排序 例 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 3、堆排序 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 3、堆排序 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 3、堆排序 （5）建堆 从一个无序序列建堆的过程就是一个反复“筛选”的过程，若将此序列看成是一个完全二叉树，则最后一个非终端结点是?n/2?个元素，由此“筛选”只需从?n/2?个元素开始。 建堆：从无序序列的第?n/2?个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选 3、堆排序 49 65 38 27 13 76 97 50 49 65 38 27 13 76 50 97 49 13 38 27 65 76 50 97 49 13 38 27 65 76 50 97 13 27 38 49 65 76 50 97 例如 含8个元素的无序序列 （49，38，65，97，76，13，27，50） 3、堆排序 时间复杂度：最坏情况下T(n)=O(nlogn) 空间复杂度：S(n)=O(1) 因为其运行时间主要耗费在建初始堆和调整新建堆时进行的反复“筛选”上。对深度为k的堆，筛选算法中进行的关键字比较次数至多为2(k-1)次。总共进行的比较的次数为：2(?log2(n-1)?+ ?log2(n-2)?+……+log22))2n(?log2n?)由此，堆排序在最坏的情况下，其时间复杂度为O(nlogn)。 相对于快速排序，此外，堆排序仅需一个记录大小供交换用，……。因此是一种适合于排序较大文件的排序方法。 堆排序是一种不稳定的排序方法。 3、堆排序 归并排序是又一类不同的排序方法。“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表 排序过程：假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1，然后两两归并，得到?n/2?个长度为2或1的有序子序列；再两两归并，……如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。 2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。——将两个或两个以上的有序表组合成一个新的有序表，叫2-路归并排序。 初始关键字： [49] [38] [65] [97] [76] [13] [27] 一趟归并后： [38 49] [65 97] [13 76] [27]