C语言数据结构-第08讲排序.ppt

《C语言数据结构-第08讲排序.ppt》由会员分享，可在线阅读，更多相关《C语言数据结构-第08讲排序.ppt（59页珍藏版）》请在金锄头文库上搜索。

1、实用数据结构基础 第9章 排序 第9章 排 序 知 识 点 排序的基本概念 插入排序方法 直接选择排序 二分插入 排序 快速排序 选择排序 归并排序 各种排序方法性能比较 难 点 堆排序 快速排序 归并排序 要 求 熟练掌握以下内容 熟悉各种内部排序方法的基本思想和 特点 各种排序方法的优缺点及性能比较 熟悉并掌握一些基本的排序算法 了解以下内容 二路归并排序算法 堆排序算法 第9章 目录 9 1 概述 9 2 插入排序 9 3 快速排序 9 4 选择排序 9 5 归并排序 9 6 各种排序方法比较 小 结 实验9 排序子系统 习题9 9 1 概 述 1 排序 Sorting 将数据元素 或记

2、录 的任意序列 重新排列成一个按 关键字有序 递增或递减 的序列的过程称为排序 2 排序过程中的两种基本操作 1 比较两个关键字值的大小 2 根据比较结果 移动记录的位置 3 对关键字排序的三个原则 1 关键字值为数值型的 则按键值大小为依据 2 关键字值为ASCII码 则按键值的内码编排顺序为依 据 3 关键字值为汉字字符串类型 则大多以汉字拼音的字 典次序为依据 4 排序方法的稳定和不稳定 若对任意的数据元素序列 使用某个排序方法 对它 按关键字进行排序 若对原先具有相同键值元素间的位置 关系 排序前与排序后保持一致 称此排序方法是稳定的 反之 则称为不稳定的 例如 对数据键值为 5 3

3、8 3 6 6 排序 若排序后的序列为 3 3 5 6 6 8 其相同键值 的元素位置依旧是3在3前 6在6前 与排序前保持一致 则表示这种排序法是稳定的 若排序后的序列为 3 3 5 6 6 8 则表示这种 排序法是不稳定的 5 待排序记录的三种存储方式 1 待排序记录存放在地址连续的一组存储单元上 类似于线性表的顺序存储结构 2 待排序记录存放在静态链表中 记录之间的次序关系由指针指示 排序不需要移动记录 3 待排序记录存放在一组地址连续的存储单元 同时另 设一个指示各个记录存储位置的地址向量 在排序过程中不 移动记录本身 而移动地址向量中这些记录的 地址 在 排序结束后 再按照地址向量中

4、的值调整记录的存储位置 6 内排序 整个排序过程都在内存进行的排序称为内排序 7 外排序 待排序的数据元素量大 以致内存一次不能容纳全部记 录 在排序过程中需要对外存进行访问的排序称为外排序 9 2 插入排序 9 2 1 直接插入排序 1 基本思想 直接插入排序 Straight Insertion Sort 是一种最 简单的排序方法 它的基本操作是将一个记录插到已排序好 的有序表中 从而得到一个新的 记录数增1的有序表 插入前 1 3 5 8 2 7 4 9 6 有序 无序 插入后 1 2 3 5 8 7 4 9 6 有序 无序 2 例 例9 19 1 输入元素序列为 输入元素序列为 393

5、9 2828 5555 8080 7575 6 6 1717 4545 2828按从小到大的序列排序 按从小到大的序列排序 第一个取第一个取3939 作第一个假设有序的记录 第二 作第一个假设有序的记录 第二 个取个取2828 28 3928 39 则交换 则交换 此后 每取来一个记录就与有序表最后一个关此后 每取来一个记录就与有序表最后一个关 键字比较 若大于或等于最后一个关键字 则插入键字比较 若大于或等于最后一个关键字 则插入 在其后 若小于最后一个关键字 则把取来的记录在其后 若小于最后一个关键字 则把取来的记录 再与前一个关键字比较再与前一个关键字比较 其过程如图 其过程如图9 19

6、 1 排序以后 相同关键字元素的28和28与排序前 的位置保持一致 即28仍然在28之前 所以直接插 入排序方法是稳定的 监视哨 哨兵 的作用 1 在进入确定插入位置的循环之前 保存了插入 值r i 的副本 避免因记录的移动而丢失r i 中的 内容 2 使内循环总能够结束 以免循环过程中数组下 标越界 3 算法 void Insertsort for i 2 i L i 依次插入r 2 r 3 r n if R i key R i 1 key R 0 R i 置监视哨 j i 1 while R 0 key275 在后半区找继续 2 再与后半区中间位置 的关键字比较 653 512 再 继续在

7、后半区找 3 再与后半区中间位置 的关键字比较 653 897 经 三次比较找到插入位置 然后插入653 二分插入排序辅助空间和直接插入相同 为O 1 从时间上比较 二分插入仅减少了比较次数 而记录的移 动次数不变 时间复杂度仍为O n2 二分插入排序是稳定的排序方法 3 算法 void BInsSort for i 2 i n i r 0 r i 将r I 暂存到r 0 while low high 在r low high 中折半查找有序插入的位置 m low high 2 折半 if r 0 key high 1 j r j 1 r j 记录后移 r high 1 r 0 插入 9 2 3

8、 希尔排序 Shell s Sort 希尔排序又称 缩小增量排序 它也是一种插入排序的 方法 但在时间上较前两种排序方法有较大的改进 1 基本思想 先将整个待排序记录序列分割成若干子序列分别进行直 接插入排序 待整个序列中的记录 基本有序时 再对全体 记录进行一次直接插入排序 特点 子序列不是简单的逐段分割 而是将相隔某个 增量 的记录组成一个子序列 所以关键字较小的记录不是 一步一步地前移 而是跳跃式前移 从而使得在进行最后一 趟增量为1的插入排序时 序列已基本有序 只要做少量比 较和移动即可完成排序 时间复杂度较低 2 例9 3 待排序列为 40 30 60 80 70 10 20 40

9、50 05 设增量分别取5 3 1 则排序过程如下 希尔排序是不稳定的排序 3 算法 void Shellsort gap n 2 初次增量取序列元素个数n的一半为步长 while gap 0 for i gap 1 i0 if r j r j gap x r j r j r j gap r j gap x j j gap 对子序列作直接插入排序 else j 0 gap gap 2 每次减半 直至步长为一 4 效率分析 希尔排序的分析是一个复杂的问题 因为它的 时间是所取 增量 序列的函数 这涉及一些数学 上尚未解决的难题 到目前为止尚未求得一种最好 的增量序列 有人在大量实验的的基础推出

10、当n 在某个特定范围内希尔排序所需的比较和移动次数 约为n1 3 所以其平均时间复杂度约为O n1 3 其辅助空间为O 1 希尔排序是不稳定的排序方法 返 回 9 3 快速排序法 9 3 1 冒泡排序 Bubble Sort 1 基本思想 冒泡法也称沉底法 每相邻两个记录关键字比大小 大 的记录往下沉 也可以小的往上浮 每一遍把最后一个 下沉的位置记下 下一遍只需检查比较到此为止 到所有 记录都不发生下沉时 整个过程结束 每交换一次 记录 减少一个反序数 2 例9 4 一个数组存有83 16 9 96 27 75 42 69 34等 9个值 在开始时83与16互相比较 因83 16 所以两元素

11、互 换 然后83 9 83与9互换 接着83 96 所以不变 然后互换 的元素有 96 27 96 75 96 42 96 69 96 34 所以在第一 趟排序结束时找到最大的值96 把它放在最下面的位置 过程如表9 1所示 表格中粗体字表示正在比较 重复每一趟排序都会将最大的一个元素放在工作区 域的最低位置 且每趟排序的工作区域都比前一趟排序 少一个元素 如此重复直至没有互换产生才停止 如表9 2所示 3 算法 void Bubblesort for i 1 i i 1 j if R j key R j 1 key 小则交换 R 0 key R j key R j key R j 1 key

12、 R j 1 key R 0 key 4 效率分析 空间效率 仅用了一个辅助单元 空间复杂度为O 1 时间效率 总共要进行n 1趟冒泡 对j个记录的表进行 一趟冒泡需要j 1次关键字的比较 移动次数 最好情况下 待排序列已有序 不需移动 最坏情况下 每次比较后均要进行三次移动 移动次数 时间复杂度为 O n2 冒泡排序是一种稳定排序 9 3 2 快速排序 Quick Sort 1 基本思想 就排序时间而言 快速排序被认为是一种最好的内部排 序方法 通过一趟快速排序将待排序的记录组分割成独立的 两部分 其中前一部分记录的关键字均比枢轴记录的关键字 小 后一部分记录的关键字均比枢轴记录的关键字大

13、枢轴 记录得到了它在整个序列中的最终位置并被存放好 这个过 程称为一趟快速排序 第二趟再分别对分割成两部分子序列 再进行快速排序 这两部分子序列中的枢轴记录也得到了 最终在序列中的位置而被存放好 并且它们又分别分割出独 立的两个子序列 显然 这是一个递归的过程 不断进 行下去 直到每个待排序的子序列中只有一个记录时为止 整个排序过程结束 快速排序是对冒泡排序的一种改进 这里有个问题 就是如何把一个记录组分成两个部分 通常是以序列中第一个记录的关键字值作为枢轴记录 2 具体做法 设待排序列的下界和上界分别为low和high R low 是 枢轴记录 一趟快速排序的具体过程如下 1 首先将R lo

14、w 中的记录保存到pivot变量中 用两个整 型变量i j分别指向low和high所在位置上的记录 2 先从j所指的记录起自右向左逐一将关键字和pivot key 进行比较 当找到第1个关键字小于pivot key的记录时 将 此记录复制到i 所指的位置上去 3 然后从i 1所指的记录起自左向右逐一将关键字和 pivot key进行比较 当找到第1个关键字大于pivot key的记 录时 将该记录复制到j所指的位置上去 4 接着再从j 1所指的记录重复以上的 2 3 两步 直到i j为止 此时将pivot中的记录放回到i 或j 的位 置上 一趟快速排序完成 3 例9 5 对数据序列 70 75

15、 69 32 88 18 16 58进行快速排序 4 算法 int Partition int i int j i j为形参 分别代表low和high RecType pivot R i while i j 从表的两端交替地向中间扫描 while i pivot key j if i j R i R j while i j if i j R j R i R i pivot return i void QuickSort int low int high 递归形式的快排序 int pivotpos k if low high pivotpos Partition low high 调用Parti

16、tion low high 函数 QuickSort low pivotpos 1 对低子表递归排序 QuickSort pivotpos 1 high 对高子表递归排序 5 效率分析 空间效率 快速排序是递归的 每层递归调用时的指 针和参数均要用栈来存放 递归调用层次数与上述二叉树 的深度一致 因而 存储开销在理想情况下为O log2n 即 树的高度 在最坏情况下 即二叉树是一个单链 为O n 时间效率 在n个记录的待排序列中 一次划分需要约 n次关键码比较 时效为O n 若设T n 为对n个记录的待 排序列进行快速排序所需时间 理想情况下 每次划分 正好将分成两个等长的子序 列 则时间复杂度为O nlog2n 最坏情况下 快速排序每次划分 只得到一个子序列 这时快速排序蜕化为冒泡排序的过程 其时间复杂度最 差 为O n2 快速排序是通常被认为在同数量级 O nlog2n 的排 序方法中平均性能最好的 快速排序是一个不稳定的排序方法 返 回 选择排序主要是从待排序列中选取一个关键字值最小的 记录 把它与第一个记录交换存储位置 使之成为有序 然 后在余下的无序的记录中 再选出关键字最小