国家级精品课程—《数据结构与算法》 第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)： 线性表 ❑ 由记录组成