《数据结构排序》PPT课件.ppt

第十章排序 内容提要 本课主题 排序的概念 插入排序 冒泡排序 快速排序 选择排序 堆排序 归并排序 其它排序方法教学目的 掌握排序的基本概念 掌握插入排序 冒泡排序 快速排序 选择排序 堆排序 归并排序算法 了解其它排序方法教学重点 插入排序 冒泡排序 快速排序 选择排序 堆排序 归并排序教学难点 快速排序 堆排序 一 排序概述 排序 将一个数据元素的无序序列重新排列成一个按关键字有序的序列 下图所示给出了两组按年龄排序的结果 注意其中有两个人的年龄相同 排序的稳定性 键值相等的记录排序前后相对顺序不变的排序方法是稳定的 键值相等的记录排序前后相对顺序可能更改的排序方法是不稳定的 提问 上图所示两个排序其稳定性怎样 前者不确定 后者不稳定一般稳定性不重要 但是有些特殊场合 如银行 司法 招生等特别关心先后顺序的场合要注意稳定性问题 排序的分类 内部排序 待排序记录存放在计算机的内存中进行的排序过程 外部排序 待排序记录数量很大 以致内存一次不能容纳全部记录 在排序过程中需对外存进行访问的排序过程 外部排序的效率主要取决于外存的访问频度 排序方法分类 排序方法 构造二叉排序树本身也是一个排序过程交换排序 起泡排序 快速排序 选择排序 简单选择排序 堆排序 插入排序 直接插入排序 希尔排序 归并排序基数排序 二 交换排序 1 起泡排序 冒泡排序 每一趟都从头部 或尾部 开始依次交换相邻逆序记录 直到在某趟排序过程中没有进行过交换记录的操作为止 冒泡排序 voidBubbleSort SqList 注意无else语句 冒泡排序 算法2 参见P16 改进方法 一旦某趟没有进行过交换操作则排序结束 设置change标志标识之 voidBubbleSort SqList 注意无else语句 结束条件是该趟没有进行过交换操作 冒泡排序性能分析 性能分析 比较操作 O n2 移动操作 O n2 辅助空间 1 稳定性 稳定提问 对整数序列32154进行从小到大的排序 经过一趟冒泡排序之后的序列怎样 完成排序至少需要多少趟 答 13245 3趟 从左到右时 21345 3趟 问题 如何增加交换的跨度以提高性能 快速排序 2 快速排序提问 编写算法将线性表中所有负数排在非负数前 要求时间复杂度 空间复杂度越低越好 比较n次 移动2n次 空间2n 比较n次 移动2n次 空间n 比较n次 最多移动1 5n次 空间1 比较n次 最多移动n 1次 空间1 快速排序 每一趟排序以某个元素为基准将待排记录分割成独立的两部分 小于基准的记录放在基准的前面 大的放在后面 该基准称之为枢轴 例如以第一个元素为基准 经一趟排序后期望达到的效果如图 下一趟排序 由于比较操作将局限在各部分内进行 不会与整个表中每个元素逐一比较 比较次数会逐趟减半 趟次也大大减少 如图 快速排序 提问 1 快速排序稳定吗 为什么 答 不稳定 例如如果元素27是38 2 对整数序列32154 45124736 34323432进行从小到大的排序 求经过一趟快速排序 划分 后的序列 答 12354 32144756 223334343 对恰好有序或逆序的序列进行一趟划分 求元素移动次数 答 恰好有序时2次 恰好无序时3次 4 编写算法将线性表中所有负数排在非负数之前 答 借助划分的思路 或前几页最后一个方法 如图 但不一定好 比较n次 最多移动n 1次 空间1 比较n次 最多移动n 1次 空间1 快速排序 划分算法的整体思路 Partition L 暂存枢轴 t L r low while low high 从右向左找关键字比枢轴小的元素移动该元素 L r low L r high 从左向右找关键字比枢轴大的元素移动该元素 L r high L r low 枢轴归位 L r low t intPartition SqList 或为if low high L r low L r high 但不能省略if判断 否则上一句while循环最后是执行 high时 返回的low值有问题 注意不能省略两处比较中的等号 否则死循环 快速排序 voidQSort SqList 对枢轴高端子表递归排序 例子程序参见 sort cpp 快速排序 性能分析 平均时间复杂度 O nlogn 最坏时 如序列恰好有序或恰好逆序时为 O n2 辅助空间 O logn 最坏时为O n 实现递归算法需要栈空间 最坏时会递归n层 但注意存储记录的辅助空间只需要1个稳定性 不稳定 三 选择排序 1 简单选择排序每一趟从第i到第n个元素中选取关键字最小的记录将其放到第i个位置 如最小记录与第i个记录交换 简单选择排序 算法1 voidSelect Sort SqList 将该记录与第i个记录交换 简单选择排序 算法2 P277 voidSelect Sort SqList 将该记录与第i个记录交换 例子程序参见 sort cpp 简单选择排序 提问 1 简单选择排序稳定吗 答 上述算法不稳定 如首元素为38时 但找到最小元素后若将其插入到目标位置 则算法是稳定的 2 对整数序列32154进行从小到大的排序 经过一趟简单选择排序之后的序列怎样 答 12354 如果采用顺序移动策略 则为13254简单选择排序与冒泡排序的区别 交换数量减少 趟次增加 不稳定 问题 如何提高选择的速度以提高性能 树形选择排序 2 树形选择排序引言 如何减少简单选择排序的比较次数 第二趟找最小的元素时利用前一趟的比较结果 例如 49 38 65 97 76 13 27 49 第一趟中存在的比较 49 38 38 65 38 97 38 76 38 13 13 27 13 49 决出冠军13之后 选亚军只需要比较38 27 49 因49 65 97 76已与38比较过 如果把两两比较作为一种数据间的关系 该操作可以用下图形象表示 树形选择排序 树形选择排序 锦标赛排序 首先对n个记录的关键字进行两两比较 然后在其中一半较小者之间再进行两两比较 如此重复 直到选出最小关键字的记录为止 利用树形结构很容易理解和实现 注意该方法与通过构造二叉排序树来排序不同 二叉排序树的非终端结点存储有真正的记录 堆排序 3 堆排序引言 树形选择排序需要构建一个完全二叉树 不是满二叉树 为什么 非终端结点并不存储元素 辅助空间多 改进方法 让每个结点都存储元素 最紧凑的方法是使用完全二叉树的顺序存储结构 为了让树根关键字值最小 需要改进策略 答 是 小顶堆 堆排序 堆 n个元素的序列 k1 k2 kn 当且仅当满足下列关系时 称之为堆 小顶堆 ki k i 2 i 2 3 n 理解 它对应的二叉树中各结点都小于两个孩子结点 故不是二叉排序树 提问 序列123456是堆吗 堆排序 利用堆可以搜寻最小元素 进而可用来排序 方法是输出堆顶元素 如把堆顶元素与最末元素交换 然后把剩余元素调整为堆 再输出堆顶元素 再调整 利用堆排序要解决两个问题 如何由一个无序序列建成一个堆 初建堆输出堆顶元素后 如何调整剩余元素成为一个新的堆 堆调整或筛选 堆排序 问题2的解决方法 注 排序思路 按图示过程不断对小顶堆进行输出堆调整 各趟堆调整全部结束以后 整个序列将变成一个从大到小的有序序列 堆排序 问题1的解决方法 基于堆调整完成初建堆 堆排序 算法 注 要使排序结果从小到大 要建立大顶堆 typedefSqListHeapType voidHeapAdjust HeapType 把首元素放到目标位置 堆调整结束 堆排序 voidHeapSort HeapType 重新调整除尾元素外的剩余元素为堆 堆排序只需1个记录大小的辅助空间 堆排序 提问 1 整数序列12345组成的小顶堆 其首元素输出后 一趟堆调整的结果如何 答 243512 整数序列32154初建堆的结果如何 答 小顶堆 12354 大顶堆 54123堆排序性能分析 时间复杂度 O nlogn 空间复杂度 O 1 稳定性 不稳定 四 插入排序 1 直接插入排序每一趟将一个新记录插入到已排好序的有序表中 从而得到一个新的 记录数增1的有序表 直接插入排序 算法1 voidInsertSort SqList 直接插入排序 算法2 P265 插入元素需要移动元素 但可以顺次移动元素 使用哨兵 voidInsertSort SqList 把元素L r i 插入到正确位置 例子程序参见 sort cpp 直接插入排序 提问 对整数序列32154进行从小到大的排序 经过一趟直接插入排序之后的序列怎样 答 23154性能分析 比较操作 顺序查找O n2 移动操作 顺序移动O n2 时间复杂度 O n2 辅助空间 1 稳定性 稳定 直接插入排序 改进方法 折半插入排序 折半查找 顺序插入 2 路插入排序 折半查找 2路插入 以首元素为基准 将剩余元素分成两个部分排序 可减少插入操作 表插入排序 基于链表顺序查找 修改指针代替移动记录 希尔排序 2 希尔排序 缩小增量排序 直接插入排序在n很小和序列基本有序时都很高效 故可以把记录大跨度方式分组 组内排序之后 整个序列便基本有序 然后缩小跨度继续分组 排序 希尔排序 希尔排序需要选择恰当的增量序列 至少应当令其互质 且最后一个增量必须是1 希尔排序不稳定 希尔排序的规律比较复杂 时间复杂度可以近似认为是n1 3 其高效的原因源于元素的跳跃式移动 算法参见课本P272 希尔排序 提问 对整数序列32154进行从小到大的排序 经过一趟希尔排序 增量为3 之后的序列怎样 答 32154 原封不动 增量为2时结果为 12354 增量为1时结果为 12345 虽只1趟 但蜕化为插入排序 五 归并排序 将两个或两个以上的有序表组合成一个新的有序表的方法叫归并 假设初始序列含有n个记录 则可看成是n个有序的子序列 每个子序列的长度为1 然后两两归并 得到n 2个长度为2或1的有序子序列 再两两归并 如此重复 由于归并排序需要的辅助空间较多 内部排序很少使用归并排序方法 归并排序 归并排序的实现 注意是先等分 再等分 直到表长为1以后才开始归并 且是对相邻子表进行归并 voidMerge ElemTypeSR ElemType TR inti intm intn 归并有序表SR i m 和SR m 1 n 为TR i n 思路类似于P26程序 不同之处是该算法是归并一个表的两个部分 而不是归并两个表 归并排序 voidMSort ElemTypeSR ElemType 归并有序表TR2 s m 和TR2 m 1 t 归并排序 voidMergeSort SqList 例子程序参见 sort cpp 为方便阅读 此例完全没考虑空间问题 纯粹参考用 归并排序 提问 对整数序列32154135进行从小到大的排序 经过一趟归并排序之后的序列怎样 答 23151435性能分析 时间复杂度 O nlogn 空间复杂度 O n 稳定性 稳定 注意 归并排序常用于外部排序 很少用于内部排序 六 基数排序 基数排序 借助多关键字的排序的思想对单关键字进行排序 七 总结 总结 记忆方法 冒炮 泡 躲飞机 基 把树插入堆 快速做选择 希尔凯旋归 经典算法 快速排序 归并操作 直接插入排序中使用哨兵 冒泡排序中使用交换标志n较大时平均时间性能 快速排序 归并排序 堆排序 希尔排序 各种O n2 类简单排序 n较小或基本有序时 直接插入排序最快通过 关键字比较 实现排序其性能极限为O nlogn 级 总结 O n2 类简单排序除选择排序外皆稳定 注意该结论也是有争议的 见P289 选择排序如果通过移动元素的方式实现元素的插入或以链表做存储结构 它也是稳定的排序方法 O nlogn 类高级