第七章内排序 任课教员:张铭 http://db.pku.edu.cn/mzhang/ds/ zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究
第七章 内排序 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究
大纲 7.1基本概念 72三种0(n2)的简单排序 插入排序 直接插入排序 二分法插入排序 冒泡排序 选择排序 73She排序 北京大学信息学院 版权所有,转载或翻印必究 Page 2
北京大学信息学院 ©版权所有，转载或翻印必究 Page 2 大纲 ◼ 7.1 基本概念 ◼ 7.2 三种Ｏ(n2)的简单排序 ◼ 插入排序 ◼ 直接插入排序 ◼ 二分法插入排序 ◼ 冒泡排序 ◼ 选择排序 ◼ 7.3 Shell排序
大纲(续) 74基于分治法的排序 n快速排序 归并排序 75堆排序 76分配排序和基数排序 77各种排序算法的理论和实验时 间代价 78排序问题的下限 北京大学信息学院 版权所有,转载或翻印必究 Page 3
北京大学信息学院 ©版权所有，转载或翻印必究 Page 3 大纲（续） ◼ 7.4 基于分治法的排序 ◼ 快速排序 ◼ 归并排序 ◼ 7.5 堆排序 ◼ 7.6 分配排序和基数排序 ◼ 7.7 各种排序算法的理论和实验时 间代价 ◼ 7.8 排序问题的下限
71基本概念 记录( Record):结点,进行排序的基 本单位 关键码(Key):唯一确定记录的一个 或多个域 排序码( Sort Key):作为排序运算依 据的一个或多个域 序列 Sequence:线性表,由记录组 成的集合 北京大学信息学院 版权所有,转载或翻印必究 Page
北京大学信息学院 ©版权所有，转载或翻印必究 Page 4 7.1基本概念 ◼ 记录(Record)：结点，进行排序的基 本单位 ◼ 关键码(Key)：唯一确定记录的一个 或多个域 ◼ 排序码(Sort Key)：作为排序运算依 据的一个 或多个域 ◼ 序列(Sequence)：线性表，由记录组 成的集合
7.1基本概念(续) 排序( Sorting)一将序列中的记 录按照排序码特定的顺序排列起 来,即排序码域的值具有不减 (或不增)的顺序。 北京大学信息学院 版权所有,转载或翻印必究 Page 5
北京大学信息学院 ©版权所有，转载或翻印必究 Page 5 7.1基本概念（续） ◼ 排序(Sorting) — 将序列中的记 录按照排序码特定的顺序排列起 来，即排序码域的值具有不减 (或不增)的顺序