数据结构与算法 大纲 71基本概念 第七章内排序 ■72三种O(m2)的简单排序 73She排序 任课教员:张铭 ■74基于分治法的排序 http://db.pku.edu.cn/mzhang/ds/ 75堆排序 mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 76分配排序和基数排序 网络与信息系统研究 77排序算法的理论和实验时间代价 ⊙版权所有,转载或翻印必究 28排序回题的下限 排序问题 小规模的排序问题 ■ Google等搜索引擎返回结果排级 图书馆员书目编号、上架 个元素 各种排名 已经有序了 考试成绩排名 两个元素 福布斯》富豪榜 次比较 Windows资源管理器,文件查看 若逆序? 次交换=3次移动(赋值) n个元素? 北大影_歌张写 权质有轨国邮究 张铭编写 有,神剑究 排序算法的分类1 排序算法的分类2 插入排 自底向上求解 交换排序、She排序 三种o(m2)的简单排序 插入排序、冒泡排序、选择排序 She排序 ■选择排序 堆排序 直接选择排序、堆排序 归并排序 自顶向下求解:基于分治法的排序 ■分配排序 归并排序、快速排序 自底向上:低位优先LsD 分配排序 页向下:高位优先MSD 自底向上:低位优先LsD ■地址排序 自顶向下:高位优先MSD 北大张写 权所有轨康■命邮 _张铭编写 新有,种究1 数据结构与算法 第七章 内排序 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 大纲 „ 7.1 基本概念 „ 7.2 三种Ｏ(n2)的简单排序 „ 7.3 Shell排序 „ 7.4 基于分治法的排序 „ 7.5 堆排序 „ 7.6 分配排序和基数排序 „ 7.7 排序算法的理论和实验时间代价 „ 7.8 排序问题的下限 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 排序问题 „ Google等搜索引擎返回结果排级 „ 图书馆员书目编号、上架 „ 各种排名 „ 大学排名 „ 考试成绩排名 „ 《福布斯》 富豪榜 „ Windows资源管理器，文件查看 „ www.kooxoo.com „ …… 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 小规模的排序问题 „ 一个元素 „ 已经有序了 „ 两个元素 „ 一次比较 „ 若逆序？ „ 一次交换 = 3次移动（赋值） „ n个元素？ 45 34 45 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 排序算法的分类1 „ 插入排序 „ 直接插入排序、Shell排序 „ 交换排序 „ 冒泡排序、快速排序 „ 选择排序 „ 直接选择排序、堆排序 „ 归并排序 „ 分配排序 „ 自底向上：低位优先LSD „ 自顶向下：高位优先MSD „ 地址排序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 排序算法的分类2 „ 自底向上求解 „ 三种Ｏ(n2)的简单排序 „ 插入排序、冒泡排序、选择排序 „ Shell排序 „ 堆排序 „ 自顶向下求解：基于分治法的排序 „ 归并排序、快速排序 „ 分配排序 „ 自底向上：低位优先LSD „ 自顶向下：高位优先MSD