hanfeng.name

I am a software engineer with interests in web applications.

排序

前言

本文是记录北京大学在Coursera上的《高级数据结构与算法》的课程。

排序

基本概念

  • 序列 Sequence:线性表 :有记录组成
  • 记录 Record: 结点,进行排序的基本单位
  • 关键码Key: 唯一确定记录的一个或多个域
  • 排序码 Sort Key: 作为排序运算依据的一个或多个域

排序:

  • 将序列中的记录 Record 按照排序码顺序排列起来
  • 排序码Sort Key域的值具有不减(或不增)的顺序

内排序:

  • 整个排序过程在内存中完成

<= 不减序

= 不增序

正序

逆序

稳定性:

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

稳定性的证明: 形式证明

不稳定的证明: 反例说明

衡量标准:

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

Comments