数据结构课件第十章2.ppt

第10章 内部排序 10.2 插入排序 课堂练习： 原始序列： 256，301，751，129，937，863，742，694，076，438 原始序列： 256，301，751，129，937，863，742，694，076，438 时间效率： 希尔排序算法（其中某一趟的排序操作） 对前页程序中间for循环的理解： 10.3 交换排序 1) 冒泡排序 冒泡排序的算法分析 2） 快速排序 例1：关键字序列 T=(21，25，49，25*，16，08），请写出快速排序的算法步骤。 例2：关键字序列 T=(21，25，49，25*，16，08），计算机如何实现快速排序算法的某一趟过程？ 例3：以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法的各趟排序结束时，关键字序列的状态。 一趟快速排序算法流程图 整个快速排序的递归算法： 讨论2. “快速排序”是否真的比任何排序算法都快？ 10.4 选择排序 1）简单选择排序 例：关键字序列T= （21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。 简单选择排序的算法如下：（亦可参见教材P276） 2） 锦标赛排序 (又称树形选择排序) 第一趟： 第二趟： 第三趟： 第四趟： 第五趟： 第六趟： 第七趟： 算法分析： 3） 堆排序 例： 2. 怎样建堆？ 建堆算法 (等同于堆排序算法中的第一步） 针对结点 i 的堆调整函数HeapAdjust 表述如下： 3. 怎样进行整个序列的堆排序？ 例：对刚才建好的大根堆进行排序： 堆排序的算法 堆排序算法分析： 课堂练习 课堂练习： 08 21 08 08 63 25* 21 21 25 49 25* 16 08 63 16 16 16 63 21 25 25 25 25* 25* r[6] Winner (胜者) 49 49 49 08 21 08 08 63 25* 21 21 25 49 25* 16 08 63 16 16 16 63 21 25 25 25 25* 25* 49 49 49 r[7] Winner (胜者) 63 锦标赛排序构成的树是完全(满）二叉树，其深度为 ?log2n ? +1，其中 n 为待排序元素个数。 时间复杂度：O(nlog2n) —n个记录各自比较约log2n次 空间效率： O(n） —胜者树的附加内结点共有n0-1个！ 稳定性：稳定 —可事先约定左结点“小” 讨论：锦标赛排序巧妙利用了第一次和前若干次扫描的结果，加快了排序速度。还有没有同类方法？ 答：有！请看—— n0 =2k = 叶子总数 堆排序 1. 什么是堆？ 堆的定义：设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。 ki ≤ k2i ki ≤ k2i+1 ki ≥ k2i ki ≥ k2i+1 或者 i=1, 2,… n/2 解释：如果让满足以上条件的元素序列 （k1，k2，…，kn）顺次排成一棵完全二叉树，则此树的特点是： 树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。 2. 怎样建堆？ 3. 怎样堆排序？ 08 25 46 49 58 67 2 3 4 5 6 1 （大根堆） 91 85 66 76 58 67 2 3 4 5 6 1 55 7 有序列T1=（08, 25, 49, 46, 58, 67）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判断它们是否 “堆”？ √ （小根堆） √ （小顶堆） （最小堆） （大顶堆） （最大堆） 终端结点（即叶子）没有任何子女，无需单独调整 步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。 21 25 25* 49 16 08 1 2 3 4 5 6 例：关键字序列T= (21，25，49，25*，16，08），请建大根堆。 解：为便于理解，先将原始序列画成完全二叉树的形式： 这样可以很清晰地从?n/2?开始调整。 完全二叉树的第一个非终端结点编号必为?n/2? ！！(性质5) 21 i=3: 49 而且21还应当向下比较！！ 49大于08，不必调整； i=2: 25大于25*和16，也不必调整； i=1: 21小于25和49，要调整！ void HeapSort (HeapType H ) { //H是顺序表，含有H.r[ ]和H.length两个分量 for ( i = length / 2; i 0; - - i ) //把r[1…length