第10讲 内部排序2.ppt

锦标赛排序构成的树是满(完全)二叉树，其深度为 ?log2n? +1， 其中 n 为待排序元素个数。 时间复杂度：O(nlog2n) —n个记录各自比较约log2n次 空间效率： O(n） —胜者树的附加内结点共有n-1个！ 稳定性：稳定 —左右结点相同者左为先 10.4.3 堆排序 1. 什么是堆? 设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。 如果让满足以上条件的元素序列 （k1，k2，…，kn）顺次排成一棵完全二叉树，则此树的特点是： 树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。 ki ≤ k2i ki ≤ k2i+1 ki ≥ k2i ki ≥ k2i+1 或者 i=1, 2, … , n/2 有序列T1=(08, 25, 49, 46, 58, 67)和序列T2=(91, 85, 76, 66, 58, 67, 55)，判断它们是否 “堆”？ 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 （大根堆） √ （小根堆） √ （小顶堆） （最小堆） （大顶堆） （最大堆） 2. 怎样建堆？ T1=(21, 25, 49, 25*, 16, 08) 从最后一个非终端结点（n/2）开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。 21 25 25* 49 16 08 1 2 3 4 5 6 完全二叉树的最后一个非终端结点编号必为?n/2? ！！(性质5) 21 i=3: 49大于08，不必调整； i=2: 25大于25*和16，也不必调整； i=1: 21小于25和49，要调整！ 49 而且21还应当向下比较！！ 3. 怎样进行堆排序？ 关键：将堆的当前顶点输出后，如何将剩余序列重新调整为堆？ 方法：将当前顶点与堆尾记录交换，然后仿建堆动作重新调整成堆，如此反复直至排序结束。 08 25 21 25* 16 49 交换 1号与 6 号记录 49 25 25* 21 16 08 1 2 3 4 5 6 49 25 21 25* 16 08 初始最大堆 25 25* 16 21 1 3 6 5 4 2 08 49 16 25* 21 08 25 49 交换 1号与 5 号记录 08 25 21 25* 16 49 从 1 号到 5 号 重新 调整为最大堆 08 25 25* 21 16 49 1 2 3 4 5 6 16 25* 08 25 21 49 1 3 6 5 4 2 08 25 25* 25 08 21 25* 16 49 08 25 25* 21 08 16 49 08 16 21 25* 25 49 交换 1 号与 4 号记录 16 25* 21 08 25 49 从 1号到 4号 重新 调整为最大堆 16 25* 08 21 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 25* 16 25* 16 21 08 25 49 08 16 21 25* 25 49 交换 1号与3 号记录 从 1 号到 3号 重新 调整为最大堆 08 16 25* 21 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 21 08 08 16 21 25* 25 49 21 16 08 25* 25 49 08 16 21 25* 25 49 交换 1 号与2 号记录 08 16 21 25* 25 49 从 1 号到 2 号 重新 调整为最大堆 08 16 25* 21 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 16 08 16 08 21 25* 25 49 时间效率： O(nlog2n)。因为整个排序过程中需要进行n-1次堆调整，而堆调整本身耗时为log2n；建堆过程比较次数不超过4n。 空间效率：O(1)。仅在交换记录时用到一个临时变量。 稳定性： 不稳定。 优点：对小文件效果不明显，但对大文件有效。 最坏情况下时间复杂度也不超过O(nlog2n). 需要在大批数据中挑出若干个最小或最大的元素时，效率较高。 9.5 归并排序 基本思想：将两个（或以上）的有序表组成新的有序表。 更实际的意义：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，首先做两两归并，得到 ?n / 2? 个长度为 2 的子序列 ；再做两两归并，