【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 (逆序)

二、排序的稳定性

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

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

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

三、排序算法的衡量标准

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

四、思考

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

参考资料

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

这里是一个广告位,,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn