数据结构课件第10章排序.ppt

Page1 2020 2 24 第十章内部排序 学习目标理解排序的定义和各种排序方法的特点 并能加以灵活应用 排序方法有不同的分类方法 基于 关键字间的比较 进行排序的方法可以按排序过程所依据的不同原则分为插入排序 交换排序 选择排序 归并排序和计数排序等五类 掌握各种排序方法的时间复杂度的分析方法 能从 关键字间的比较次数 分析排序算法的平均情况和最坏情况的时间性能 按平均时间复杂度划分 内部排序可分为三类 O n2 的简单排序方法 O n logn 的高效排序方法和O d n 的基数排序方法 理解排序方法 稳定 或 不稳定 的含义 弄清楚在什么情况下要求应用的排序方法必须是稳定的 Page2 2020 2 24 重点和难点重点 希尔排序 快速排序 堆排序和归并排序等高效方法难点 希尔排序 快速排序 堆排序和归并排序等高效方法知识点排序 直接插入排序 折半插入排序 表插入排序 希尔排序 起泡排序 快速排序 简单选择排序 堆排序 2 路归并排序 基数排序 排序方法的综合比较 Page3 2020 2 24 10 1概述 排序假设含有n个记录的序列为 R1 R2 Rn 它们的关键字相应为 K1 K2 Kn 对记录序列进行排序就是要确定序号1 2 n的一种排列P1 P2 Pn 使其相应的关键字满足如下的非递减 或非递增 的关系 Kp1 Kp2 Kpn使序列成为一个按关键字有序的序列 Rp1 Rp2 Rpn 目的利用高效的查找方法 以提高查找效率 Page4 2020 2 24 排序分类按待排序记录所在位置内部排序 待排序记录存放在内存 外部排序 排序过程中需对外存进行访问的排序 按排序依据原则插入排序 直接插入排序 折半插入排序 希尔排序 交换排序 冒泡排序 快速排序 选择排序 简单选择排序 堆排序 归并排序 2 路归并排序 基数排序 Page5 2020 2 24 稳定若待排序文件中有关键字相等的记录 排序后 其前后相对次序与排序前未发生变化 这种排序称为 稳定 排序 否则是 不稳定 排序 稳定排序与不稳定排序只是表示所用的排序方法 并不说明哪种方法好与差 排序基本操作比较两个关键字大小 将记录从一个位置移动到另一个位置 就全面性能而言 很难提出一种被认为最好的方法 每种方法均有优点和适用环境 Page6 2020 2 24 本章讨论中 待排记录如下结构 defineMAXSIZE20 假设的顺序表最大长度typeintKeyType 定义关键字类型为整数类型typedefstruct KeyTypekey 关键字项InfoTypeotherinfo 其它数据项 RcdType 记录类型typedefstruct RcdTyper MAXSIZE 1 r 0 闲置或作为判别标志的 哨兵 单元intlength 顺序表长度 SqList 顺序表类型 Page7 2020 2 24 10 2插入排序 10 2 1直接插入排序基本思想整个排序过程为n 1趟插入 即先将序列中第1个记录看成是一个有序子序列 然后从第2个记录开始 逐个进行插入 直至整个序列有序 Page8 2020 2 24 49386597761327 i 2 49 386597761327 i 3 3849 6597761327 i 4 384965 97761327 i 5 38496597 761327 i 6 3849657697 1327 i 1 i 7 133849657697 27 27 97 76 65 49 38 27 38 38 49 65 97 97 76 97 76 13 76 65 49 38 13 监视哨 稳定的排序方法 Page9 2020 2 24 voidInsertSort SqList 插入到正确位置 if InsertSort 直接插入排序的算法 12345678 时间复杂度T n O n Page10 2020 2 24 算法评价时间复杂度若待排序记录按关键字从小到大排列 正序 关键字比较次数 记录移动次数 若待排序记录按关键字从大到小排列 逆序 关键字比较次数 记录移动次数 Page11 2020 2 24 若待排序记录是随机的 取平均值 关键字比较次数 记录移动次数 空间复杂度S n O 1 Page12 2020 2 24 10 2 2其它插入排序 折半插入排序基本思想用折半查找方法确定插入位置的排序 i 1 30 1370853942620 i 213 1330 70853942620 i 76 6133039427085 20 i 820 6133039427085 20 i 820 613203039427085 Page13 2020 2 24 voidBInsertSort SqList 插入 BInsertSort 时间复杂度 T n O n Page14 2020 2 24 算法评价时间复杂度 T n O n 空间复杂度 S n O 1 折半插入排序只能减少排序过程中关键字比较的时间 并不能减少记录移动的时间 Page15 2020 2 24 2 路插入排序基本思想另设一个和L r同类型的数组d 首先将L r 1 赋给d 1 并将d 1 看成是在排好序的序列中处于中间位置的记录 然后从L r中第2个记录起依次插入到d 1 之前或之后的有序序列中 目的对折半插入排序的改进 减少记录的移动次数 Page16 2020 2 24 初始关键字 4938659776132749 i 1 49 i 2 49 38 i 3 4965 38 i 4 496597 38 Page17 2020 2 24 初始关键字 4938659776132749 i 4 496597 38 i 5 49657697 38 i 6 49657697 1338 i 7 49657697 132738 Page18 2020 2 24 初始关键字 4938659776132749 i 7 49657697 132738 i 8 2路插入排序的移动记录次数减少了 约为n2 8 但不能避免移动 Page19 2020 2 24 10 2 3希尔 shell 排序 基本思想是对插入排序的一个改进 也称缩小增量排序 先将整个待排序记录序列分割成若干个子序列 分别对这些子序列进行直接插入排序 待整个序列中的记录 基本有序 时 再对全体记录进行一次直接插入排序 排序过程取一个正整数d1 n 把所有相隔d1的记录放一组 组内进行直接插入排序 然后取d2 d1 重复上述分组和排序操作 直至di 1 即所有记录放进一个组中排序为止 Page20 2020 2 24 初始关键字 49 38 65 97 76 13 27 49 55 4 取d3 1三趟分组 三趟排序结果 一趟排序结果 二趟排序结果 取d1 5一趟分组 取d2 3二趟分组 不稳定的排序方法 Page21 2020 2 24 一趟希尔排序算法10 4 voidShellInsert SqList 插入 if ShellInsert Page22 2020 2 24 希尔排序的算法10 5 voidShellSort SqList ShellSort 希尔排序的时间复杂度和所取增量序列相关 例如已有学者证明 当增量序列为2t k 1 k 0 1 t 1 时 希尔排序的时间复杂度为O n3 2 Page23 2020 2 24 希尔排序特点子序列的构成不是简单的 逐段分割 而是将相隔某个增量的记录组成一个子序列 希尔排序可提高排序速度 因为分组后n值减小 n 更小 而T n O n 所以T n 从总体上看是减小了 关键字较小的记录跳跃式前移 在进行最后一趟增量为1的插入排序时 序列已基本有序 增量序列取法无除1以外的公因子 最后一个增量值必须为1 如 9 5 3 2 1或 31 15 7 3 1或 40 13 4 1等 Page24 2020 2 24 10 3交换排序 起泡排序排序过程将第一个记录的关键字与第二个记录的关键字进行比较 若为逆序r 1 key r 2 key 则交换 然后比较第二个记录与第三个记录 依次类推 直至第n 1个记录和第n个记录比较为止 第一趟冒泡排序 结果关键字最大的记录被安置在最后一个记录上 对前n 1个记录进行第二趟冒泡排序 结果使关键字次大的记录被安置在第n 1个记录位置重复上述过程 直到 在一趟排序过程中没有进行过交换记录的操作 为止 Page25 2020 2 24 初始关键字 49 76 97 13 97 27 97 97 13 76 76 27 13 65 27 65 65 13 13 49 49 27 38 27 38 38 76 时间复杂度最好情况 正序 比较次数 n 1移动次数 0最坏情况 逆序 比较次数 空间复杂度 S n O 1 移动次数 Page26 2020 2 24 快速排序对起泡法的一种改进 基本思想通过一趟排序 将待排序记录分割成独立的两部分 其中一部分记录的关键字均比另一部分记录的关键字小 则可分别对这两部分记录进行排序 以达到整个序列有序 Page27 2020 2 24 排序过程对r s t 中记录进行一趟快速排序 附设两个指针i和j 设枢轴记录rp r s x rp key 初始时令i s j t 首先 从j所指位置向前搜索第一个关键字小于x的记录 并和rp交换 再从i所指位置起向后搜索 找到第一个关键字大于x的记录 和rp交换 重复上述两步 直至i j为止 再分别对两个子序列进行快速排序 直到每个子序列只含有一个记录为止 Page28 2020 2 24 27 初始关键字 65 13 97 49 不稳定的排序方法 Page29 2020 2 24 一趟快速排序的算法10 6 intPartition SqList 返回枢轴位置 Partition Page30 2020 2 24 快速排序算法10 7和10 8 voidQsort SqList 对高子表排序 Qsort voidQuickSort SqList QuickSort 时间复杂度T n O n Page31 2020 2 24 算法分析时间复杂度最好情况 每次总是选到中间值作枢轴 T n O nlog2n 最坏情况 每次总是选到最小或最大元素作枢轴 T n O n 为防止最差情况的出现 一般采取 三者取中 法来确定枢轴 即在第一个记录和最后一个记录 以及中间位置的记录中 选取值为中间的那个来作枢轴 这样就能防止最差情况的出现 空间复杂度 需栈空间以实现递归最坏情况 S n O n 一般情况 S n O log2n 对随机的关键字序列 快速排序是目前被认为是最好的排序方法 Page32 2020 2 24 10 4选择排序 基本思想每一趟在n i 1 i 1 2 n 1 个记录中选取关键字最小的记录 并将它和第i个记录进行互换 从而使其成为有序序列中第i个记录 10 4 1简单选择排序排序过程首先 通过n 1次关键字比较 从n个记录中找出关键字最小的记录 将它与第一个记录交换 再通过n 2次比较 从剩余的n 1个记录中找出关键字次小的记录 将它与第二个记录交换 重复上述操作 共进行n 1趟排序后 排序结束 Page33 2020 2 24 i 1 13 49 i 2 27 38 i 3 i 4 i 5 i 6 38 65 49 97 76 65 97 76 97 排序结束 稳定的排序方法 Page34 2020 2 24 简单选择排序算法10 9 voidSelectSort SqList 与第i个记录互换 for SelectSort 时间复杂度T n O n Page35 2020 2 24 算法评价时间复杂度记录移动次数最好情况 0最坏情况 3 n 1 比较次数 空间复杂度 S n O 1 Page36 2020 2 24 10 4 3堆排序 堆的定义n个元素的序列 k1 k2 kn 当且仅当满足下列关系时 称之为堆 或 若将此序列对应的一维数组看成是一个完全二叉树 则ki为二叉树的根结点 k2i和k2i 1分别为ki的 左子树根 和 右子树根 Page37 2020 2 24 96 83 27 38 11 9 13 38 27 50 76 65 49 97 大顶堆 小顶堆 Page38 2020 2 24 堆排序将无序序列建成一个堆 得到关键字最小 或最大 的记录 输出堆顶的最小 大 值后 使剩余的n 1个元素重又建成一个堆 则可得到n个元素的次小值 重复执行 得到一个有序序列的过程 堆排序需解决的两个问题 如何由一个无序序列建成一个堆 初始建堆 如何在输出堆顶元素之后 调整剩余元素 使之成为一个新的堆 Page39 2020 2 24 第二个问题解决方法 筛选 以小顶堆为例 输出堆顶元素之后 以堆中最后一个元素替代之 然后将根结点值与左 右子树的根结点值进行比较 并与其中小者进行交换 重复上述操作 直至叶子结点 将得到新的堆 称这个从堆顶至叶子的调整过程为 筛选 Page40 2020 2 24 Page41 2020 2 24 Page42 2020 2 24 Page43 2020 2 24 筛选算法10 10 voidHeapAdjust SqList 回移筛选下来的记录 HeapAdjust 若改为小顶堆 该如何修改语句 j m LT H r j 1 key H r j key LT rc key H r j key Page44 2020 2 24 第一个问题解决方法从无序序列的第 n 2 个元素 即此无序序列对应的完全二叉树的最后一个非终端结点 起 至第一个元素止 进行反复筛选 例如 含8个元素的无序序列 49 38 65 97 76 13 27 50 Page45 2020 2 24 例如 含8个元素的无序序列 49 38 65 97 76 13 27 50 Page46 2020 2 24 堆排序算法10 11 voidHeapSort SqList 将H r 1 i 1 重新调整为 大顶堆 for HeapSort Page47 2020 2 24 算法评价时间复杂度 最坏情况下T n O nlogn 筛选算法 最多从第1层筛到最底层 为完全二叉树的深度 log2n 1 初始建堆 调用筛选算法 n 2 次 重建堆 调用筛选算法n 1次 空间复杂度 S n O 1 记录较少时 不提倡使用 不稳定的排序方法 Page48 2020 2 24 10 5归并排序 归并将两个或两个以上的有序表组合成一个新的有序表 2 路归并排序排序过程设初始序列含有n个记录 则可看成n个有序的子序列 每个子序列长度为1 两两合并 得到 n 2 个长度为2或1的有序子序列 再两两合并 如此重复 直至得到一个长度为n的有序序列为止 Page49 2020 2 24 初始关键字 49 38 65 97 76 13 27 一趟归并后 3849 6597 1376 27 二趟归并后 38496597 132776 三趟归并后 13273849657697 稳定的排序方法 Page50 2020 2 24 两个有序序列归并为一个有序序列的算法10 12 voidMerge RcdTypeSR RcdType 将剩余的SR j n 复制到TR Merge Page51 2020 2 24 算法评价时间复杂度 T n O nlog2n 每趟两两归并需调用merge算法 n 2h 次 h为有序段长度 整个归并要进行 log2n 趟 空间复杂度 S n O n Page52 2020 2 24 10 6基数排序 10 6 1多关键字的排序多关键字排序 例对52张扑克牌按以下次序排序 两个关键字 花色 面值 2 3 A 并且 花色 地位高于 面值 2 3 A 2 3 A 2 3 A 2 3 A Page53 2020 2 24 多关键字排序方法最高位优先法 MSD 先对最高位关键字k1排序 将序列分成若干子序列 每个子序列有相同的k1值 然后让每个子序列对次关键字k2 如面值 排序 又分成若干更小的子序列 依次重复 直至就每个子序列对最低位关键字kd排序 最后将所有子序列依次连接在一起成为一个有序序列 最低位优先法 LSD 从最低位关键字kd起进行排序 然后再对高一位的关键字排序 依次重复 直至对最高位关键字k1排序后 便成为一个有序序列 Page54 2020 2 24 MSD与LSD不同特点按MSD排序 必须将序列逐层分割成若干子序列 然后对各子序列分别排序 按LSD排序 不必分成子序列 对每个关键字都是整个序列参加排序 并且可不通过关键字比较 而通过若干次分配与收集实现排序 Page55 2020 2 24 10 6 2链式基数排序 基数排序一种借助 多关键字排序 的思想来实现 单逻辑关键字排序 的内部排序算法 基数排序的步骤设置10个队列 f i 和e i 分别为第i个队列的头指针和尾指针 第一趟分配对最低位关键字 个位 进行 改变记录的指针值 将链表中记录分配至10个链队列中 每个队列记录的关键字的个位相同 第一趟收集是改变所有非空队列的队尾记录的指针域 令其指向下一个非空队列的队头记录 重新将10个队列链成一个链表 重复上述两步 进行第二趟 第三趟分配和收集 分别对十位 百位进行 最后得到一个有序序列 Page56 2020 2 24 初始状态 一趟收集 Page57 2020 2 24 二趟收集 一趟收集 Page58 2020 2 24 三趟收集 二趟收集 稳定的排序方法 Page59 2020 2 24 算法评价时间复杂度 分配 T n O n 收集 T n O rd T n O d n rd 其中 n 记录数d 关键字数rd 关键字取值范围空间复杂度 S n 2rd个队列指针 n个指针域空间 Page60 2020 2 24 10 7各种内部排序方法的比较讨论 时间性能按平均的时间性能来分 有三类排序方法 时间复杂度为O nlogn 的方法有 快速排序 堆排序和归并排序 其中快速排序目前被认为是最快的一种排序方法 后两者之比较 在n值较大的情况下 归并排序较堆排序更快 时间复杂度为O n2 的有 插入排序 起泡排序和选择排序 其中以插入排序为最常用 特别是对于已按关键字基本有序排列的记录序列尤为如此 选择排序过程中记录移动次数最少 时间复杂度为O n 的排序方法基数排序 Page61 2020 2 24 当待排记录序列按关键字顺序有序时 插入排序和起泡排序能达到O n 的时间复杂度 而对于快速排序而言 这是最不好的情况 此时的时间性能蜕化为O n2 因此应尽量避免 选择排序 堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变 以上对排序的时间复杂度的讨论主要考虑排序过程中所需进行的关键字间的比较次数 当待排序记录中其它各数据项比关键字占有更大的数据量时 还应考虑到排序过程中移动记录的操作时间 有时这种操作的时间在整个排序过程中占的比例更大 从这个观点考虑 简单排序的三种排序方法中起泡排序效率最低 Page62 2020 2 24 空间性能指的是排序过程中所需的辅助空间大小 所有的简单排序方法 包括 插入 起泡和选择排序 和堆排序的空间复杂度均为O 1 快速排序为O logn 为递归程序执行过程中栈所需的辅助空间 归并排序和基数排序所需辅助空间最多 其空间复杂度为O n 排序方法的稳定性能除希尔排序 快速排序和堆排序是不稳定的排序方法外 本章讨论的其它排序方法都是稳定的 稳定性 是由方法本身决定的 一般来说 排序过程中所进行的比较操作和交换数据仅发生在相邻的记录之间 没有大步距的数据调整时 则排序方法是稳定的 Page63 2020 2 24 Page64 2020 2 24 本章小结 一般来说 在选择排序方法时 可有下列几种选择 若待排序的记录个数n值较小 例如n 30 则可选用插入排序法 但若记录所含数据项较多 所占存储量大时 应选用选择排序法 若待排序的记录个数n值较大时 应选用快速排序法 但若待排序记录关键字有 有序 倾向时 就慎用快速排序 而宁可选用堆排序或归并排序 而后两者的最大差