【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

Sam avatar
About Sam
专注生物信息 专注转化医学