排序问题 给定一个序列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)