第七章内排序 任课教员:张铭 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) — 将序列中的记 录按照排序码特定的顺序排列起 来，即排序码域的值具有不减 (或不增)的顺序
排序问题 给定一个序列R={r1r2 ●● },其 排序码分别为k≡{k,k2,…,kn 排序的目的就是将R中的记录按照特定的 顺序重新排列,形成一个新的有序序列 R'={r1,r'2 ●●● a相应排序码为k={k1,92 ,k,ny 其中k1≤k2≤≤k或k1≥ ,≥k, 前者称为不减序,后者称为不增序。 北京大学信息学院 版权所有,转载或翻印必究 Page 6
北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 排序问题 ◼ 给定一个序列R ={r1, r2, …，rn}，其 排序码分别为k ={k1, k2, …，kn} ◼ 排序的目的就是将R中的记录按照特定的 顺序重新排列，形成一个新的有序序列 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 ， 前者称为不减序，后者称为不增序
71基本概念(续) a内排序( Internal Sorting):整个 排序过程中所有的记录都可以直 接存放在内存中 外排序( External Sorting):内存 无法容纳所有记录,排序过程中 还需要访问外存 北京大学信息学院 版权所有,转载或翻印必究 Page 7
北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 7.1基本概念（续） ◼ 内排序(Internal Sorting)：整个 排序过程中所有的记录都可以直 接存放在内存中 ◼ 外排序(External Sorting)：内存 无法容纳所有记录，排序过程中 还需要访问外存
7.1基本概念(续) “正序”序列:待排序序列正好 符合排序要求 “逆序”序列:把待排序序列 逆转过来,正好符合排序要求 北京大学信息学院 版权所有,转载或翻印必究 Page 8
北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 7.1基本概念（续） ◼ “正序”序列 ：待排序序列正好 符合排序要求 ◼ “逆序” 序列 ：把待排序序列 逆转过来，正好符合排序要求
7.1基本概念(续) “稳定的”( stable排序算法:如 果存在多个具有相同排序码的记 录,经过排序后这些记录的相对 次序仍然保持不变。 北京大学信息学院 版权所有,转载或翻印必究 age 9
北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 7.1基本概念（续） ◼ “稳定的”(stable)排序算法 ：如 果存在多个具有相同排序码的记 录，经过排序后这些记录的相对 次序仍然保持不变
排序算法的分类 简单排序 插入排序( Insert sort) 直接选择排序( Selection sort 冒泡排序( Bubble sort) aShe排序( Shell sort) 北京大学信息学院 版权所有,转载或翻印必究 Page 10
北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 排序算法的分类 ◼ 简单排序 ◼ 插入排序(Insert sort) ◼ 直接选择排序(Selection sort) ◼ 冒泡排序(Bubble sort) ◼ Shell排序(Shell sort)