【8.1】内排序--排序问题的基本概念
一、基本概念
- 序列 (Sequence):线性表
- 由记录组成
- 记录 (Record):结点,进行排序的基本单位
- 关键码 (Key):唯一确定记录的一个或多个域
- 排序码 (Sort Key):作为排序运算依据的一个 或多个域
什么是排序?
- 排序
- 将序列中的记录按照排序码顺序排列起来
- 排序码域的值具有不减(或不增)的顺序
- 内排序
- 整个排序过程在内存中完成
排序问题
给定一个序列 R = { r1, r2, …,rn }
- 其排序码分别为 k = { k1, k2, …,kn }
排序的目的:将记录按排序码重排
- 形成新的有序序列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 ,称为不增序
正序 vs. 逆序
- “正序”序列 :待排序序列正好符合排序要求
“逆序”序列 :把待排序序列逆转过来,正好 符合排序要求
例如,要求不升序列
- 08 12 34 96 (正序)
- 96 34 12 08 (逆序)
二、排序的稳定性
- 稳定性
- 存在多个具有相同排序码的记录
- 排序后这些记录的相对次序保持不变
稳定性的证明——形式化证明
不稳定性的证明——反例说明
三、排序算法的衡量标准
- 时间代价:记录的比较和移动次数
- 空间代价
- 算法本身的繁杂程度
四、思考
- 排序算法的稳定性有何意义?
- 为何需要考虑“正序”与“逆序”序列?
参考资料
北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾
