考研笔记

数据结构第 8 章：排序总览

算法你都会，这一章要补的是「教材口径」。 全章的分值集中在三处： 表 8.1 的每一格、由中间序列判断算法、外部排序的数数题。

页面导航

节页一句话
8.1 + 8.2排序概念与插入排序稳定性的定义 + 折半插入只省比较
8.3交换排序教材版 Partition 只有一种
8.4选择排序与堆排序统考重点；建堆从 往前
8.5归并、基数、计数排序唯一稳定的 + 唯一非比较
8.6各种内部排序算法的比较及应用全章总账，默写表 8.1
8.7.1~8.7.3外部排序与败者树只考数数：趟数、比较、I/O
8.7.4~8.7.5置换-选择排序与最佳归并树三列表 +
—📖 第 8 章名词库30 条名词 + 43 行范围限定清单

表 8.1（默写目标）

算法种类最好平均最坏空间稳定
直接插入排序是
冒泡排序是
简单选择排序否
希尔排序———否
快速排序否
堆排序否
二路归并排序是
基数排序是

希尔那三格是空的（教材：依赖增量函数，无法准确给出）；空间列只写平均（快排最坏 ）。

全章的三条线

① 六个记忆抓手

flowchart LR
    A["最好能到 O(n)<br/>直接插入 · 冒泡<br/>（都要基本有序）"]
    B["与初始状态无关<br/>简单选择 · 堆 · 归并 · 基数"]
    C["最坏会退化<br/>快速排序 O(n²)"]
    D["空间不是 O(1)<br/>快排 O(log n) · 归并 O(n) · 基数 O(r)"]
    E["稳定的四个<br/>插入 · 冒泡 · 归并 · 基数"]
    F["仅顺序存储的四个<br/>折半插入 · 希尔 · 快排 · 堆"]

    classDef g fill:#c8e6c9,stroke:#1b5e20
    classDef r fill:#ffcdd2,stroke:#b71c1c
    classDef b fill:#e3f2fd,stroke:#1565c0
    class A,E g
    class C,D r
    class B,F b

第六条的共同原因：折半插入要折半定位、希尔要跳增量、快排要双指针对撞、堆要 定位孩子——都需要 随机存取，链表做不到。 与 7.2.2 折半查找只能顺序存储 同理。

② 三个 算法的分工

时间空间稳定教材给的选择理由
快速排序平均最优，最坏 否关键字随机分布时，基于比较的内部排序算法中最好的
堆排序三档都是 否辅助空间少于快排，且不会出现快排的最坏情况
二路归并三档都是 是要求稳定且 时选它

这张表能默写，8.6.2 的「排序算法小结」就不用背了。

③ 外部排序：两条减少 I/O 的路

flowchart TD
    G["目标：减少 I/O 次数<br/>S = ⌈log_k r⌉"]
    G -->|"增大归并路数 k"| K["8.7.3 败者树<br/>使内部比较与 k 无关"]
    G -->|"减少归并段个数 r"| R["8.7.4 置换-选择排序<br/>产出比 WA 更长的归并段"]
    R --> M["8.7.5 最佳归并树<br/>段长不等时安排归并顺序"]
    K -.->|"k 过大时缓冲区变小<br/>读/写反而增加"| L["k 不是越大越好"]

    classDef root fill:#ffcdd2,stroke:#b71c1c,stroke-width:3px
    classDef norm fill:#e3f2fd,stroke:#1565c0
    classDef warn fill:#fff9c4,stroke:#f57f17
    class G root
    class K,R,M norm
    class L warn

计算模板总表

场景公式
归并趟数
外部排序总 I/O， 为磁盘块数
败者树深度；选一次最小比较 次
初始建败者树 次比较
用败者树后总比较，与 无关
最佳归并树 I/O， 内部结点权值
虚段数； 时补 个
内部归并趟数（二路归并排序）

高频边界

第一组 · 空间复杂度（最常错）

  • 快排 ，不是 （递归工作栈），最坏 。
  • 归并 ，基数 。
  • 堆排序才是 ，所以「堆排序辅助空间少于快排」。

第二组 · 最好情况

  • 直接插入、冒泡能到 （要基本有序）。
  • 简单选择恒为 ，比较次数固定 。
  • 快排最坏出现在序列已有序时。

第三组 · 唯一性结论

  • 唯一 的稳定算法：归并排序。
  • 唯一不基于比较的算法：基数排序。
  • 唯一空间与 无关的算法：基数排序（）。
  • 堆的应用只有两个：堆排序和优先队列。

第四组 · 手算动作（教材口径）

  • 教材版 Partition：枢轴取区间最后一个、填坑不 swap、先 i 向右。
  • 建堆从 往前，与较大孩子交换，交换后一路下沉。
  • 希尔排序按增量分组，组内直接插入。
  • 置换-选择的 MINIMAX 是「比上一个输出值大的最小者」。

第五组 · 外部排序

  • 总 I/O 要加内部排序阶段的 。
  • 败者树内部结点存败者，ls[0] 存冠军。
  • 不是越大越好。
  • 虚段权为 0，应离根最远；「缺额留最后」不是最佳方案。

复习顺序

  1. 8.6 — 先看这一节，把表 8.1 和四类分组过一遍，建立全章框架。
  2. 8.1~8.2 — 稳定性定义 + 折半插入的三条限定。
  3. 8.3 — 手推教材版 Partition 三遍，中间序列必须对得上。
  4. 8.4 — 统考重点。手画建堆和删除各三遍。
  5. 8.5 — 三条唯一性结论。
  6. 8.7.1~8.7.3 — 数数：趟数、I/O、败者树比较次数。
  7. 8.7.4~8.7.5 — 置换-选择的三列表 + 最佳归并树的虚段。
  8. 回到 8.6 默写表 8.1，然后扫 名词库 的 43 行清单。

只有 3 小时的话：默写表 8.1 → 手推一次教材版 Partition → 手画一次建堆 → 算一遍外部排序的 I/O 和最佳归并树 → 名词库清单。这五件事覆盖本章绝大部分分值。

链接

反向链接