一、基本概念

• 序列 (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 （逆序）

二、排序的稳定性

• 稳定性
  • 存在多个具有相同排序码的记录
  • 排序后这些记录的相对次序保持不变

稳定性的证明——形式化证明

不稳定性的证明——反例说明

三、排序算法的衡量标准

• 时间代价:记录的比较和移动次数
• 空间代价
• 算法本身的繁杂程度

四、思考

1. 排序算法的稳定性有何意义?
2. 为何需要考虑“正序”与“逆序”序列?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾