【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 (逆序)
二、排序的稳定性
- 稳定性
- 存在多个具有相同排序码的记录
- 排序后这些记录的相对次序保持不变
稳定性的证明——形式化证明
不稳定性的证明——反例说明
三、排序算法的衡量标准
- 时间代价:记录的比较和移动次数
- 空间代价
- 算法本身的繁杂程度
四、思考
- 排序算法的稳定性有何意义?
- 为何需要考虑“正序”与“逆序”序列?
参考资料
北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾
这里是一个广告位,,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn