数据结构---第十章 内部排序
第九章 内部排序
9.1 概述
9.2 插入排序
9.3 交换排序
9.4 选择排序
9.5 归并排序
9.6 基数排序
9.1 概述
9.1.1 什么是排序
是根据记录关键字的值的递增(递减)的关系将文件记录的次序重新排列.
9.1.2 排序的分类
[根据排序时文件记录的存放位置]
内部排序:排序过程中将全部记录放在内存中处理.
外部排序:排序过程中需在内外存之间交换信息.
[根据排序前后相同关键字记录的相对次序]
稳定排序:设文件中任意两个记录的关键字值相同,即Ki=Kj(i j),若排序之前记录Ri领先于记录Rj ,排序后这种关系不变(对所有输入实例而言).
不稳定排序:只要有一个实例使排序算法不满足稳定性要求.
[根据文件的存储结构划分排序的种类]
连续顺序文件排序
链表排序
地址排序: 待排记录顺序存储,排序时只对辅助表(关键字+指针)的表目进行物理重排.
[根据排序的方法]
插入排序 交换排序
选择排序 归并排序
基数排序
[根据排序算法所需的辅助空间]
就地排序: O(1) 非就地排序: O(n)或与n有关
9.1.3 评价排序算法的主要标准
[时间开销]
考察算法的两个基本操作的次数:
比较关键字
移动记录
算法时间还与输入实例的初始状态有关时,分情况:
最好
最坏
平均
[空间开销] 所需的辅助空间
讨论约定:(1)连续顺序文件 (2)关键字非递减
9.2 插入排序
9.2.1 直接插入排序(增量法)

下一页