第九章 排序(1)

第九章排序 插入排序交换排序选择排序归并排序外部排序 9 1插入排序 排序 将一个数据元素 或记录 的任意序列 重新排列成一个按关键字有序的序列 内部排序 整个排序过程完全在内存中进行 外部排序 由于待排序记录数据量太大 内存无法容纳全部数据 排序需要借助外部存储设备才能完成 称为外部排序 按排序依据原则 插入排序 直接插入排序 折半插入排序 希尔排序 交换排序 冒泡排序 快速排序 选择排序 简单选择排序 堆排序 归并排序 2 路归并排序 排序基本操作比较两个关键字大小 将记录从一个位置移动到另一个位置 排序算法的稳定性 假定在待排序的记录集中 存在多个具有相同键值的记录 若经过排序 这些记录的相对次序仍然保持不变 即在原序列中 ki kj且ri在rj之前 而在排序后的序列中 ri仍在rj之前 则称这种排序算法是稳定的 否则称为不稳定的 插入排序 基本思想 在一个已排好序的记录子集的基础上 每一步将下一个待排序的记录有序插入到已排好序的记录子集中 直到将所有待排记录全部插入为止 直接插入排序折半插入排序2路插入排序希尔排序 1 直接插入排序 基本思想 在插入第i i 1 个记录时 前面的i 1个记录已经排好序 需解决的关键问题 1 如何构造初始的有序序列 2 如何查找待插入记录的插入位置 r0123456 21 18 25 22 10 25 21 22 10 25 18 18 r 0 的作用 暂存单元 监视哨 voidInsSort RecordTyper intlength 对记录数组r做直接插入排序 length为数组的长度 for i 2 i length i r 0 r i j i 1 将待插入记录存放到r 0 中 while r 0 key r j key 寻找插入位置 r j 1 r j j j 1 将待插入记录插入到已排序的序列中 r j 1 r 0 InsSort 直接插入排序算法实现 直接插入排序算法评价 最好情况下 正序 最坏情况下 逆序 时间复杂度为O n2 时间复杂度为O n 平均情况下 随机排列 直接排序的时间复杂度为O n2 2 折半插入排序 排序过程 用折半查找方法确定插入位置的排序 例 i 1 30 1370853942620 i 213 1330 70853942620 i 76 6133039427085 20 i 820 613203039427085 折半插入排序算法实现 voidBinSort RecordTyper intlength for i 2 i low j r j 1 r j r low x 插入记录 折半插入排序算法评价 采用折半插入排序法 可减少关键字的比较次数 每插入一个元素 需要比较的次数最大为折半判定树的深度 如插入第i个元素时 设i 2j 则需进行log2i次比较 因此插入n 1个元素的平均关键字的比较次数为O nlog2n 虽然折半插入排序法与直接插入排序法相比较 改善了算法中比较次数的数量级 但其并未改变移动元素的时间耗费 所以折半插入排序的总的时间复杂度仍然是O n2 3 2路插入排序 目的减少移动记录次数 约为n2 8 使用DS 辅助向量 d 1 n 指针 first和final 当前最小和最大值位置 思想 将d 1 视为有序文件的中间记录 并将待插入记录r i key与d 1 key进行比较 若r i key d 1 key 则将r i 插入到d first d 1 之间 若r i key d 1 key 则将r i 插入到d 1 d final 之间 例如 49 38 65 97 76 13 27 49i 149firstfinali 24938finalfirsti 3496538finalfirsti 449659738finalfirst i 84949657697132738finalfirst 4 希尔排序 基本思想 将整个待排序记录分割成若干个子序列 在子序列内分别进行直接插入排序 待整个序列中的记录基本有序时 对全体记录进行直接插入排序 需解决的关键问题 1 应如何分割待排序记录 才能保证整个序列逐步向基本有序发展 2 子序列内如何进行直接插入排序 123456789 40 21 25 49 25 16 初始序列 30 08 13 defineT3intd 5 3 1 49 13 38 27 27 4 55 38 65 48 97 55 76 4 子序列的构成不是简单的 逐段分割 而是将相隔某个增量的记录组成一个子序列 希尔排序可提高排序速度 因为分组后n值减小 n 更小