考研笔记

选择排序与堆排序

教材原话：「选择排序中的堆排序是历年统考考查的重点。」 而且这一节还有一条大纲变动：

「最新 408 统考大纲增加了考点『堆的应用』，堆的应用只有两个：堆排序和优先队列。」

「只有两个」这三个字省了不少事——大纲扩了考点，但外延被教材钉死了。

机制

简单选择排序

假设排序表为 ，第 趟排序即从 中选择关键字最小的元素与 交换，每一趟排序可以确定一个元素的最终位置，这样经过 趟排序就可使得整个排序表有序。

void SelectSort(ElemType A[],int n){
    for(int i=0;i<n-1;i++){                 //一共进行 n-1 趟
        int min=i;                          //记录最小元素位置
        for(int j=i+1;j<n;j++)              //在 A[i..n-1] 中选择最小的元素
            if(A[j]<A[min]) min=j;          //更新最小元素位置
        if(min!=i) swap(A[i],A[min]);       //封装的 swap() 函数共移动元素 3 次
    }
}
指标值
空间效率仅使用常数个辅助单元，
移动次数不会超过 次，最好的情况是移动 0 次（表已有序）
比较次数与序列的初始状态无关，始终是 次
时间复杂度始终是
稳定性不稳定
适用性顺序存储和链式存储的线性表，以及关键字较少的情况

边界辨析：

教材给的不稳定反例要能背下来：表 ，经过一趟排序后 ， 最终排序序列也是 ——两个 2 的相对次序已发生变化。 这正是 8.1 说的「举一组反例即可」的标准示范。

另外注意：简单选择排序的比较次数恒为 ，与初始状态无关—— 这是它与 冒泡排序（最好 ）最常被对比的一点。

堆的定义

个关键字序列 称为堆，当且仅当该序列满足：

①且或②且
  • 可以将堆视为一棵完全二叉树。
  • 满足条件 ① 的堆称为大根堆（大顶堆），大根堆的最大元素存放在根结点，且其任意一个非根结点的值小于或等于其双亲结点值。
  • 满足条件 ② 的堆称为小根堆（小顶堆），根结点是最小元素。

边界辨析：

的范围是 ，因为只有分支结点才需要满足堆的条件。 这个 与 5.2.1 完全二叉树的「最后一个分支结点编号 」是同一个数—— 堆的一切下标运算都来自完全二叉树的编号性质。

堆排序的思路

首先将存放在 中的 个元素建成初始堆，因为堆本身的特点（以大顶堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。

堆排序需要解决两个问题：① 如何将无序序列构造成初始堆？② 输出堆顶元素后，如何将剩余元素调整成新的堆？

建堆：从 到 1

建堆思路是从后往前检查所有分支结点，看是否满足堆的要求，若不满足，则对以该分支结点为根的子树进行调整。

个结点的完全二叉树，最后一个结点是第 个结点的孩子。对以第 个结点为根的子树筛选（对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换），使该子树成为堆。之后向前依次对以各结点（）为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。

flowchart TD
    S["从 i = ⌊n/2⌋ 开始"] --> C{"L(i) ≥ 左右孩子中较大者？"}
    C -->|"是"| N["i ← i − 1"]
    C -->|"否"| X["与较大孩子交换"]
    X --> D["下沉：对被交换到的<br/>子树位置继续同样判断"]
    D --> C2{"仍破坏堆？"}
    C2 -->|"是"| X
    C2 -->|"否"| N
    N --> E{"i ≥ 1？"}
    E -->|"是"| C
    E -->|"否"| F["建堆完成"]

    classDef done fill:#c8e6c9,stroke:#1b5e20
    classDef loop fill:#ffcdd2,stroke:#b71c1c,stroke-width:2px
    classDef norm fill:#e3f2fd,stroke:#1565c0
    class F done
    class X,D,C2 loop
    class S,C,N,E norm

教材图 8.6 的例子（序列 ，，）：

步骤动作
调整 子树：，交换
调整 子树： 左右孩子的较大者 ，交换
调整 子树： 左右孩子的较大者 ，交换
调整至根结点 ：，交换；交换后破坏了 子树的堆，继续对 调整：，交换

第 4 步是全部重点：一次交换可能引发连锁下沉，必须一路调到底。

输出堆顶后的调整（删除）

输出堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，需要向下进行筛选。教材例子：将 09 和左右孩子的较大者 78 交换，交换后破坏了 子树的堆，继续对 子树向下筛选，将 09 和左右孩子的较大者 65 交换，交换后得到了新堆。

指标值
建堆时间——教材原话「可以在线性时间内完成建堆」
排序过程
最好 / 平均 / 最坏都是
空间
稳定性不稳定
适用存储仅顺序存储

关联对照：

堆排序是表 8.1 里唯一「时间 且空间 」的算法。 8.6.2 因此说：「堆排序所需的辅助空间少于快速排序，且不会出现快速排序可能的最坏情况。」 快排空间 （递归工作栈），归并空间 （辅助数组）—— 三个 算法，空间分别是 / / 。这是一组必须能立刻答出的对照。

口径差异：

算竞里堆就是 priority_queue，从不手画筛选过程；建堆用 make_heap 或直接逐个 push。 408 反复考的正是手算：「初始建堆的操作」（2018、2021）、「堆的删除操作及调整操作分析」（2015、2024）、 「堆的性质与特点」（2020）。 三个具体动作要练熟：从 往前建堆、与较大孩子交换（大根堆）、交换后一路下沉。

手算模板

建大根堆：

  1. 把序列按层序填进完全二叉树，下标从 1 开始。
  2. 从 递减到 1。
  3. 每个 ：比较 与其孩子中较大者；小于则交换，然后从被交换的孩子位置继续同样判断，直到不再交换或到达叶结点。
  4. 到 结束。

堆排序的一趟：

  1. 堆顶与最后一个元素交换（最大值就位）。
  2. 堆规模减 1。
  3. 对新堆顶向下筛选。

验算：第 趟结束后，数组末尾 个元素已是最终位置的最大 个。

边界

说法判断说明
「简单选择排序最好情况 」❌比较次数恒为 ，始终
「简单选择排序稳定」❌不稳定，反例
「简单选择排序移动次数多」❌不超过 次，比直接插入少
「简单选择排序只能用于顺序表」❌顺序和链式都可以
「堆一定是完全二叉树」✅可以将堆视为一棵完全二叉树
「大根堆的叶结点一定比所有分支结点小」❌只保证父 ≥ 子，不同分支之间没有大小关系
「堆的定义对所有 成立」❌，只对分支结点
「建堆从 开始」❌从 往前
「建堆时间是 」❌线性时间
「大根堆调整时与左孩子交换」❌与左右孩子中较大者交换
「一次交换后就完成调整」❌可能连锁下沉，要一路调到底
「堆排序空间复杂度 」❌
「堆排序稳定」❌不稳定
「堆的应用有很多」❌教材明说只有两个：堆排序和优先队列

对照速查

算法最好平均最坏空间稳定存储
简单选择否顺序 + 链式
堆排序否仅顺序
三个 算法的空间值原因
堆排序原地筛选
快速排序递归工作栈
二路归并辅助数组
堆操作起点方向
建堆从后往前，每个都可能下沉
删除（输出堆顶）堆顶最后一个元素上来，然后下沉

考点

  • 简单选择排序的比较次数恒为 、移动不超过 。
  • 简单选择排序不稳定的反例。
  • 堆的定义与 （2020 命题追踪）。
  • 初始建堆的操作（2018、2021 命题追踪）——手算重点。
  • 堆的删除操作及调整操作分析（2015、2024 命题追踪）。
  • 建堆是线性时间，排序过程 。
  • 堆的应用只有堆排序和优先队列（大纲新增考点）。
  • 三个 算法的空间对照。

链接

反向链接