数据结构与算法 第七章内排序 任课教员:张铭 http://db.pkuedu.cn/mzhang/ds zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究
数据结构与算法 第七章 内排序 任课教员:张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有,转载或翻印必究
大纲 7.1基本概念 72三种O(n2)的简单排序 73She排序 74基于分治法的排序 75堆排序 7.6分配排序和基数排序 77排序算法的理论和实验时间代价 78排序问题的下限 北京大学信息学院 铭编写 版权所有,转载或翻印必究 P
北京大学信息学院 张铭编写 ©版权所有,转载或翻印必究 Page 2 大纲 7.1 基本概念 7.2 三种O(n2)的简单排序 7.3 Shell排序 7.4 基于分治法的排序 7.5 堆排序 7.6 分配排序和基数排序 7.7 排序算法的理论和实验时间代价 7.8 排序问题的下限
排序问题 Google等搜索引擎返回结果排级 图书馆员书目编号、上架 各种排名 n大学排名 考试成绩排名 ■《福布斯》富豪榜 Windows资源管理器,文件查看 www.kooxoo.com 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 P
北京大学信息学院 张铭编写 ©版权所有,转载或翻印必究 Page 3 排序问题 Google等搜索引擎返回结果排级 图书馆员书目编号、上架 各种排名 大学排名 考试成绩排名 《福布斯》 富豪榜 Windows资源管理器,文件查看 www.kooxoo.com ……
小规模的排序问题 一个元素 45 已经有序了 两个元素 4534 次比较 若逆序? 次交换三3次移动(赋值) n个元素? 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 P
北京大学信息学院 张铭编写 ©版权所有,转载或翻印必究 Page 4 小规模的排序问题 一个元素 已经有序了 两个元素 一次比较 若逆序? 一次交换 = 3次移动(赋值) n个元素? 45 34 45
排序算法的分类1 插入排序 直接插入排序、She排序 交换排序 冒泡排序、快速排序 ■选择排序 直接选择排序、堆排序 归并排序 分配排序 自底向上:低位优先LsD 自顶向下:高位优先MsD 地址排序 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 P
北京大学信息学院 张铭编写 ©版权所有,转载或翻印必究 Page 5 排序算法的分类1 插入排序 直接插入排序、Shell排序 交换排序 冒泡排序、快速排序 选择排序 直接选择排序、堆排序 归并排序 分配排序 自底向上:低位优先LSD 自顶向下:高位优先MSD 地址排序
排序算法的分类2 ■自底向上求解 种O(n2)的简单排序 插入排序、冒泡排序、选择排序 She排序 堆排序 ■自顶向下求解:基于分治法的排序 归并排序、快速排序 分配排序 自底向上:低位优先LSD 自顶向下:高位优先MSD 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 P
北京大学信息学院 张铭编写 ©版权所有,转载或翻印必究 Page 6 排序算法的分类2 自底向上求解 三种O(n2)的简单排序 插入排序、冒泡排序、选择排序 Shell排序 堆排序 自顶向下求解:基于分治法的排序 归并排序、快速排序 分配排序 自底向上:低位优先LSD 自顶向下:高位优先MSD
711基本概念 记录 Record):结点,进行排序的基 本单位 关键码(Key):唯一确定记录的一个 或多个域 排序码( Sort Key):作为排序运算依 据的一个或多个域 序列( Sequence):线性表 由记录组成 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 Page 7
北京大学信息学院 张铭编写 ©版权所有,转载或翻印必究 Page 7 7.1.1 基本概念 记录(Record):结点,进行排序的基 本单位 关键码(Key):唯一确定记录的一个 或多个域 排序码(Sort Key):作为排序运算依 据的一个或多个域 序列(Sequence):线性表 由记录组成
什么是排序? 排序 将序列中的记录按照排序码顺序排列起来 排序码域的值具有不减(或不增)的顺序 内排序 整个排序过程在内存中完成 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 P
北京大学信息学院 张铭编写 ©版权所有,转载或翻印必究 Page 8 什么是排序? 排序 将序列中的记录按照排序码顺序排列起来 排序码域的值具有不减(或不增)的顺序 内排序 整个排序过程在内存中完成
排序问题 给定一个序列R={r1,r2…,rn} 其排序码分别为k={k,k2 排序的目的:将记录按排序码重排 形成新的有序序列R={r'1,r32,…,r2n} n相应排序码为k={k'1,k2,…,kn 排序码的顺序 其中k1≤k2≤…≤kn,称为不减序 或k1≥k2≥≥kn,称为不增序 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 P
北京大学信息学院 张铭编写 ©版权所有,转载或翻印必究 Page 9 排序问题 给定一个序列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逆序 “正序”序列:待排序序列正好符合 排序要求 逆序”序列:把待排序序列逆转过 来,正好符合排序要求 例如,要求不升序列「逆序! 08123496 96341208 正序! 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 10
北京大学信息学院 张铭编写 ©版权所有,转载或翻印必究 Page 10 正序 vs. 逆序 “正序”序列 :待排序序列正好符合 排序要求 “逆序” 序列 :把待排序序列逆转过 来,正好符合排序要求 例如,要求不升序列 08 12 34 96 96 34 12 08 逆序! 正序!