国家级精品课程—《数据结构与算法》 第8章内排序 张铭、赵海燕、王腾蛟、宋国杰、高军 http:/www.jpk.pku.edu.cn/pkujpk/course/sigl 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:张铭 ⊙版权所有,转载或翻印必究
国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：张铭 ©版权所有，转载或翻印必究 第8章 内排序
主要内容 81排序问题的基本概念 82插入排序(She排序) 8.3选择排序(堆排序 84交换排序 口841冒泡排序 口842快速排序 8.5归并排序 86分配排序和索引排序 8.7排序算法的时间代价 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主要内容 ◼ 8.1 排序问题的基本概念 ◼ 8.2 插入排序（Shell排序） ◼ 8.3 选择排序（堆排序） ◼ 8.4 交换排序 ❑ 8.4.1 冒泡排序 ❑ 8.4.2 快速排序 ◼ 8.5 归并排序 ◼ 8.6 分配排序和索引排序 ◼ 8.7 排序算法的时间代价
排序问题 文件①)编辐)查看①收滚)工具①)帮助Q ⊙后是·国的P默收,园,回自器 图书馆c 网页图片资讯地图更多》 oogle结数据结构 coy搜索高級搜索|使用偏好 各种扎 所有网页中文网页简体中文网页⊙中国的网页 网页 约有235000项符合张铭数据结构的查询结果,以下是第110项(搜索用时021秒) 口大学 北京大学信息科学技术学院《数据结构与算法》裸程视频(主讲:张铭) 欻据结构概论——概念、逻辑结构、存储结构、算法特性(张铭).pdf·第二讲.数据 考试2 口《福 张铭论著 张铭、赵海燕、王腾蛟,《欻据结构与算法一一学习指导与习题解析》,高等教 育岀版灬许卓群,杨冬青,唐世渭,张铭。《数据结构与算法》,高等教育出 indo 版社,2004年7 db. cs. pku. edu.cn/ zhang/papers/ paperlist. htm-36k-网页快照·类似网页 数据结构:[清华严蔚敏]S[北人l张铭S[电子科人罗吴蔓]--视频 综述:我看过3个数据结构的视频。清华大 、北京大学张铭的、电子科大罗 吴蔓的。其中前两个是两年前或一年前看的,电子科技大学的罗吴蔓的是新近看 www.eimhe.com/bbs/viewthread.php?id=85912-78k-网页快照-类似网页 始P收件箱二如22北大学。「张铭 因 Micron 65 收5旧8:48 “十一五”国家级规划教材。张铭,王腾蛟,赵海￡,《数据结构与算法》,高教社,2008.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 排序问题 ◼ Google等搜索引擎返回结果排级 ◼ 图书馆员书目编号、上架 ◼ 各种排名 ❑ 大学排名 ❑ 考试成绩排名 ❑ 《福布斯》 富豪榜 ◼ Windows资源管理器，文件查看 ◼ ……
小规模的排序问题 个元素 a已经有序了 5 两个元素 次比较 4534 口若逆序? 一次交换=3次移动(赋值) n个元素? “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 小规模的排序问题 ◼ 一个元素 ❑ 已经有序了 ◼ 两个元素 ❑ 一次比较 ❑ 若逆序？ ◼ 一次交换 = 3次移动（赋值） ◼ n个元素？ 45 34 45
8基本概念 记录 Record) 结点,进行排序的基本单位 关键码(Key) 唯一确定记录的一个或多个域 排序码( Sort Key) 作为排序运算依据的一个或多个域 序列( Sequence) 线性表 口由记录组成 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 8.1 基本概念 ◼ 记录(Record)： 结点，进行排序的基本单位 ◼ 关键码(Key)： 唯一确定记录的一个或多个域 ◼ 排序码(Sort Key)： 作为排序运算依据的一个或多个域 ◼ 序列(Sequence)： 线性表 ❑ 由记录组成
什么是排序? 排序 口将序列中的记录按照排序码顺序排列起来 口排序码域的值具有不减(或不增)的顺序 内排序 口整个排序过程在内存中完成 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 什么是排序？ ◼ 排序 ❑ 将序列中的记录按照排序码顺序排列起来 ❑ 排序码域的值具有不减(或不增)的顺序 ◼ 内排序 ❑ 整个排序过程在内存中完成
排序问题 给定一个序列R={r1,r2,…,rn 口其排序码分别为k={k1,k2,…,kn 排序的目的:将记录按排序码重排 口形成新的有序序列R={r1,r2,…,rn} 口相应排序码为k={k1,k32,…k3n 排序码的顺序 口其中k21≤k2≤…≤kn,称为不减序 口或k1≥k2≥…≥k’n,称为不增序 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 排序问题 ◼ 给定一个序列R ={r1, r2, …，rn} ❑ 其排序码分别为k ={k1, k2, …，kn} ◼ 排序的目的：将记录按排序码重排 ❑ 形成新的有序序列R'= {r'1,r'2,…,r'n} ❑ 相应排序码为k'={k'1,k'2,…k'n} ◼ 排序码的顺序 ❑ 其中k'1≤k'2≤…≤k'n，称为不减序 ❑ 或k'1≥k'2≥…≥k'n ，称为不增序
正序vs.逆序 “正序”序列: 待排序序列正好符合排序要求 “逆序”序列: 把待排序序列逆转过来,正好符合排 序要求 例如,要求不升序列逆序! a96341208 正序! “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 正序 vs. 逆序 ◼ “正序”序列 ： 待排序序列正好符合排序要求 ◼ “逆序”序列 ： 把待排序序列逆转过来，正好符合排 序要求 ◼ 例如，要求不升序列 ❑ 08 12 34 96 ❑ 96 34 12 08 逆序！ 正序！
排序的稳定性 稳定性 口存在多个具有相同排序码的记录 排序后这些记录的相对次序保持不变 稳定性例1 口3412340896 稳定! a08123434′96 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 排序的稳定性 ◼ 稳定性 ❑ 存在多个具有相同排序码的记录 ❑ 排序后这些记录的相对次序保持不变 ◼ 稳定性例1 ❑ 34 12 34’ 08 96 ❑ 08 12 34 34’ 96 稳定！
排序的稳定性 稳定性 存在多个具有相同排序码的记录 排序后这些记录的相对次序保持不变 稳定性例2 口3412340896 a0812343496 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 排序的稳定性 ◼ 稳定性 ❑ 存在多个具有相同排序码的记录 ❑ 排序后这些记录的相对次序保持不变 ◼ 稳定性例2 ❑ 34 12 34’ 08 96 ❑ 08 12 34’ 34 96 不稳定！