> ## Documentation Index
> Fetch the complete documentation index at: https://docs.0907world.cn/llms.txt
> Use this file to discover all available pages before exploring further.

# 第 8 章 排序

> 整理插入、交换、选择、归并、基数排序与外部排序，并汇总复杂度、稳定性和算法选择。

本章整理排序的基本概念、五类内部排序、排序算法比较与外部排序。排序是 408 中“结论密集 + 过程分析”并重的一章：内部排序要能写出每一趟排序后的序列，外部排序要围绕 I/O 次数计算。

> [!TIP]
>
> **复习主线**：每种算法先抓“怎么走一趟”和“一趟后哪些元素到位”，再记时间、空间、稳定性三个结论，最后用总表和“比较排序下界”把整章串起来。

## 排序的基本概念

> [accordion] 排序、关键字与稳定性
>
> * **排序**：将一组数据元素按关键字的大小重新排列成递增或递减序列的过程
>
> * **关键字**：数据元素中用于比较排序的属性，可以是单个数据项，也可以是若干数据项的组合
>
> * **稳定性**：若待排序表中两个关键字相同的元素 $R_i$、$R_j$（排序前 $R_i$ 在 $R_j$ 之前），排序后 $R_i$ 仍在 $R_j$ 之前，则称该排序算法**稳定**；否则称**不稳定**
>
> > [!WARNING]
> >
> > **易错点**：稳定性是算法本身的性质，与初始序列无关。不能因为某组数据排序后相同关键字次序恰好没变，就判定该算法稳定。

> [accordion] 内部排序与外部排序
>
> * **内部排序**：排序期间元素全部存放在内存中
>
> * **外部排序**：元素过多、无法一次全部放入内存，排序过程中需要不断在内存与外存之间移动数据
>   * 评价外部排序的核心指标是**外存 I/O 次数**，而不是关键字比较次数
>
> * **原地排序**：辅助空间为 $O(1)$。递归调用栈等额外空间也要计入辅助空间
>
> > [!NOTE]
> >
> > 408 中默认待排序表采用**顺序存储**（数组），可以随机访问；若改为链表，元素移动的代价和部分结论会发生变化，题目会另行说明。

> [accordion] 评价指标与算法分类
>
> | 指标 | 含义 |
> | - | - |
> | 时间复杂度 | 比较次数、移动次数等操作的数量级 |
> | 空间复杂度 | 排序过程中额外使用的辅助空间 |
> | 稳定性 | 相同关键字元素的相对位置是否改变 |
>
> **按思想分类**（本章主线）：
>
> * 插入排序：直接插入、折半插入、希尔排序
>
> * 交换排序：冒泡排序、快速排序
>
> * 选择排序：简单选择排序、堆排序
>
> * 归并排序：二路归并排序
>
> * 基数排序：按位分配与收集，**不属于比较排序**
>
> > [!TIP]
> >
> > **复习方法**：每学一种算法，都回答四个问题——怎么走一趟、一趟后哪些元素到位、时间与空间复杂度、是否稳定。

## 插入排序

插入排序的核心思想：每次把一个待排序元素插入到前面已经有序的子序列中。

> [accordion] 直接插入排序：思想与手算过程
>
> **基本思想**：
>
> 1. 初始时，把第一个元素看作长度为 1 的有序子序列
>
> 2. 从第 2 个元素起，取出当前元素 $A[i]$，在有序区 $A[1..i-1]$ 中从后向前查找插入位置
>
> 3. 比 $A[i]$ 大的元素依次后移一位
>
> 4. 把 $A[i]$ 放入空出的位置
>
> > [!TIP]
> >
> > **稳定性关键**：从后向前比较时，只有严格大于（`>`）才后移；遇到相等元素就停下，把待插入元素放在它后面，因此直接插入排序**稳定**。
>
> 以 `49 38 65 97 76 13 27` 为例，每趟插入一个元素：
>
> | 趟 | 待插入 | 插入后序列 |
> | - | - | - |
> | 初始 | — | 49 38 65 97 76 13 27 |
> | 1 | 38 | 38 49 65 97 76 13 27 |
> | 2 | 65 | 38 49 65 97 76 13 27 |
> | 3 | 97 | 38 49 65 97 76 13 27 |
> | 4 | 76 | 38 49 65 76 97 13 27 |
> | 5 | 13 | 13 38 49 65 76 97 27 |
> | 6 | 27 | 13 27 38 49 65 76 97 |
>
> 共 $n-1$ 趟；第 $i$ 趟结束后，前 $i+1$ 个元素有序。

> [accordion] 直接插入排序的复杂度与适用场景
>
> * **最好情况**：原序列已经有序，比较 $n-1$ 次、移动 0 次，时间 $O(n)$
>
> * **最坏情况**：原序列逆序，比较和移动次数均约为 $n^2/2$，时间 $O(n^2)$
>
> * **平均情况**：$O(n^2)$
>
> * **空间复杂度**：$O(1)$
>
> * **稳定性**：稳定
>
> > [!TIP]
> >
> > **适用**：$n$ 较小，或序列**基本有序**时，直接插入排序往往是最快的内部排序之一。

> [accordion] 折半插入排序：只减少比较，不减少移动
>
> **基本思想**：先用折半查找在有序区 $A[1..i-1]$ 中确定插入位置，再统一后移元素、插入。
>
> **与直接插入排序的区别**：
>
> | 比较项目 | 直接插入 | 折半插入 |
> | - | - | - |
> | 查找插入位置 | 顺序查找 | 折半查找 |
> | 比较次数 | 较多，与初始序列有关 | 约 $O(n\log n)$，与初始序列无关 |
> | 移动次数 | 与初始序列有关 | 与直接插入相同 |
> | 时间复杂度 | $O(n^2)$ | $O(n^2)$ |
> | 空间复杂度 | $O(1)$ | $O(1)$ |
> | 稳定性 | 稳定 | 稳定 |
>
> > [!WARNING]
> >
> > **高频陷阱**：折半插入只优化了“找位置”，没有优化“挪元素”。元素移动次数仍可能达到 $O(n^2)$，因此总时间复杂度仍是 $O(n^2)$，不是 $O(n\log n)$。
>
> > [!NOTE]
> >
> > **稳定性的细节**：为保证稳定，折半查找应定位到“最后一个不大于待插入元素的元素之后”，使相等元素排在待插入元素之前。

> [accordion] 希尔排序：缩小增量，分组插入
>
> **基本思想**：取一个增量 $d$，把相隔 $d$ 的元素分成一组，各组分别做直接插入排序；然后缩小 $d$，重复；当 $d=1$ 时对整个序列做一次直接插入排序。
>
> **增量序列的要求**：
>
> * 最后一个增量必须为 1，否则不能保证最终有序
> * 增量之间通常取互质，避免同一元素在同一组内反复出现，减少重复劳动
>
> 以 `49 38 65 97 76 13 27 49` 为例，取增量 $4 \to 2 \to 1$：
>
> | 趟 | 增量 | 分组 | 本趟结果 |
> | - | - | - | - |
> | 1 | 4 | (49,76) (38,13) (65,27) (97,49) | 49 13 27 49 76 38 65 97 |
> | 2 | 2 | (49,27,76,65) (13,49,38,97) | 27 13 49 38 65 49 76 97 |
> | 3 | 1 | 整个序列做直接插入排序 | 13 27 38 49 49 65 76 97 |
>
> > [!NOTE]
> >
> > **为什么最后一趟必须是 $d=1$**：只有增量为 1 时，整个序列才作为一组参与插入排序；前面的分组排序只是让序列“更接近有序”，并不能保证全局有序。

> [accordion] 希尔排序的复杂度与稳定性
>
> | 指标 | 结论 |
> | - | - |
> | 时间复杂度 | 与增量序列有关；常见最坏为 $O(n^2)$，好的增量序列可优于 $O(n^2)$ |
> | 空间复杂度 | $O(1)$ |
> | 稳定性 | **不稳定** |
>
> **为什么不稳定**：相同关键字的元素可能被分到不同的子序列，跨组移动后相对次序会被打乱。
>
> > [!WARNING]
> >
> > **考点**：希尔排序是直接插入排序的改进，但**不再是稳定排序**；不能因为直接插入稳定就认为希尔也稳定。

## 交换排序

交换排序的核心思想：通过交换两个元素的位置，使关键字逐渐满足排序要求。

> [accordion] 冒泡排序：每趟「沉」一个最值
>
> **基本思想**：从前往后依次比较相邻元素，若逆序则交换；一趟结束后，最大元素“冒”到末尾，有序区从后向前扩大。
>
> **关键点**：
>
> * 每趟至少确定一个元素的最终位置，最多 $n-1$ 趟
> * 若某一趟没有发生交换，说明序列已经有序，可以提前结束
> * 相等元素不交换，因此**稳定**
>
> 以 `49 38 65 97 76 13 27 49` 为例（从前往后、大数下沉）：
>
> | 趟 | 比较范围 | 本趟结果 |
> | - | - | - |
> | 初始 | — | 49 38 65 97 76 13 27 49 |
> | 1 | 全部 | 38 49 65 76 13 27 49 **97** |
> | 2 | 前 7 个 | 38 49 65 13 27 49 **76 97** |
> | 3 | 前 6 个 | 38 49 13 27 49 **65 76 97** |
> | 4 | 前 5 个 | 38 13 27 49 **49 65 76 97** |
> | 5 | 前 4 个 | 13 27 38 **49 49 65 76 97** |
> | 6 | 前 3 个 | 13 27 38 49 49 65 76 97（无交换，提前结束） |
>
> 第 6 趟没有发生交换，说明序列已经有序，可以提前结束；最坏情况下才需要 $n-1$ 趟。

> [accordion] 冒泡排序的复杂度
>
> * **最好情况**：正序且设置提前结束标志，比较 $n-1$ 次，时间 $O(n)$
>
> * **最坏情况**：逆序，比较 $n(n-1)/2$ 次，移动 $3n(n-1)/2$ 次，时间 $O(n^2)$
>
> * **平均情况**：$O(n^2)$
>
> * **空间复杂度**：$O(1)$
>
> * **稳定性**：稳定
>
> > [!NOTE]
> >
> > **与简单选择排序对比**：冒泡的交换次数可能很多；简单选择的交换次数最多 $n-1$ 次，但比较次数固定。两者最坏时间同为 $O(n^2)$。

> [accordion] 快速排序：分治与一趟划分
>
> **基本思想**（分治）：
>
> 1. 选择一个枢轴 `pivot`（常取第一个元素）
> 2. 一趟划分：把序列分成左右两部分，左边元素都不大于枢轴，右边元素都不小于枢轴
> 3. 枢轴落到最终位置
> 4. 对左右子序列递归执行上述过程
>
> **一趟划分的双指针做法**：
>
> * 用 `low`、`high` 分别指向待划分区间的两端，`pivot = A[low]`
> * 先从 `high` 向左找第一个**小于** `pivot` 的元素，填入 `A[low]`，`low` 右移
> * 再从 `low` 向右找第一个**大于** `pivot` 的元素，填入 `A[high]`，`high` 左移
> * 重复直到 `low == high`，把 `pivot` 放入该位置
>
> 以 `49 38 65 97 76 13 27 49` 为例，取首元素 49 为枢轴：
>
> | 步骤 | 操作 | 序列 |
> | - | - | - |
> | 初始 | 枢轴 49，low=1，high=8 | 49 38 65 97 76 13 27 49 |
> | 1 | high 找到 27，填 low | 27 38 65 97 76 13 \* 49 |
> | 2 | low 找到 65，填 high | 27 38 \* 97 76 13 65 49 |
> | 3 | high 找到 13，填 low | 27 38 13 97 76 \* 65 49 |
> | 4 | low 找到 97，填 high | 27 38 13 \* 76 97 65 49 |
> | 5 | low 与 high 相遇于 4，填枢轴 | 27 38 13 **49** 76 97 65 49 |
>
> 表中 `*` 表示当前的待填位置；第 5 步把枢轴放入，得到最终划分结果。
>
> > [!TIP]
> >
> > **记忆**：一趟划分的结果一定是“左小右大 + 枢轴归位”。枢轴左边的元素不一定有序，右边也不一定有序，但分别都不大于、不小于枢轴。

> [accordion] 快速排序的复杂度与考点
>
> | 情况 | 时间复杂度 | 原因 |
> | - | - | - |
> | 最好 | $O(n\log n)$ | 每次划分基本均衡 |
> | 平均 | $O(n\log n)$ | 划分较为均衡 |
> | 最坏 | $O(n^2)$ | 每次划分极不均衡 |
>
> * **空间复杂度**：平均 $O(\log n)$，最坏 $O(n)$，来自递归调用栈
> * **稳定性**：不稳定
>
> **高频考点**：
>
> 1. 每趟划分后，**枢轴元素到达最终位置**，但左右子序列内部仍可能无序
>
> 2. 递归深度取决于划分是否均衡；最坏退化为 $0$ 与 $n-1$ 两部分，递归深度 $O(n)$
>
> 3. 待排序序列**基本有序**（正序或逆序）且取首元素为枢轴时，最坏 $O(n^2)$
>
> 4. 快速排序的平均性能在比较排序中最好，但最坏情况不如堆排序、归并排序稳定
>
> 5. 枢轴优化：随机选取、三数取中，可降低出现最坏情况的概率
>
> > [!WARNING]
> >
> > **易错**：快速排序的空间复杂度不是 $O(1)$；递归调用栈也要计入辅助空间。

## 选择排序

选择排序的核心思想：每一趟从待排序序列中选出最小（或最大）元素，放到最终位置。

> [accordion] 简单选择排序：每趟选最小，交换到前面
>
> **基本思想**：第 $i$ 趟从 $A[i..n]$ 中选出最小元素，与 $A[i]$ 交换；$n-1$ 趟后全部有序。
>
> * **比较次数**：固定为 $n(n-1)/2$，**与初始序列无关**
>
> * **移动次数**：最多 $n-1$ 次交换，即 $3(n-1)$ 次移动
>
> * **时间复杂度**：最好、平均、最坏均为 $O(n^2)$
>
> * **空间复杂度**：$O(1)$
>
> * **稳定性**：**不稳定**
>
> > [!WARNING]
> >
> > **不稳定的例子**：`2 2 1`。第一趟把第一个 `2` 与 `1` 交换，得到 `1 2 2`，两个 `2` 的相对次序被改变。

> [accordion] 堆的定义与顺序存储
>
> * **大根堆**：每个结点的值都不小于其左右孩子的值，堆顶为最大值
> * **小根堆**：每个结点的值都不大于其左右孩子的值，堆顶为最小值
> * 堆是一棵**完全二叉树**，通常采用顺序存储
>
> 若采用从 1 开始的数组下标，对结点 $i$：
>
> $$
> 左孩子 = 2i,\qquad 右孩子 = 2i+1,\qquad 双亲 = \left\lfloor \frac{i}{2} \right\rfloor
> $$
>
> > [!NOTE]
> >
> > 若采用从 0 开始的下标，则左孩子为 $2i+1$、右孩子为 $2i+2$、双亲为 $\lfloor (i-1)/2 \rfloor$。做题时先看题目约定。
>
> > [!TIP]
> >
> > **升序排序用大根堆**：每次把堆顶（最大值）换到数组末尾，堆的有效长度减 1，最终得到升序序列。降序排序则用小根堆。

> [accordion] 建堆：从最后一个非叶结点向前调整
>
> **建堆过程**：从最后一个非叶结点 $\lfloor n/2 \rfloor$ 开始，依次向前对每个结点执行**向下调整**。
>
> > [!NOTE]
> >
> > **为什么建堆是 $O(n)$**：越靠近叶子的结点越多，但需要向下调整的高度越低；总代价约为 $\sum 2^h \cdot (H-h)$ 量级，最终为 $O(n)$，不是 $O(n\log n)$。
>
> 以 `53 17 78 9 45 65 87` 建大根堆：
>
> | 步骤 | 调整结点 | 序列 |
> | - | - | - |
> | 初始 | — | 53 17 78 9 45 65 87 |
> | 1 | $i=3$（78） | 53 17 **87** 9 45 65 78 |
> | 2 | $i=2$（17） | 53 **45** 87 9 17 65 78 |
> | 3 | $i=1$（53） | **87** 45 **78** 9 17 65 53 |
>
> 第 3 步中，53 先与 87 交换，再继续向下与 78 交换，才得到最终结果。
>
> 建堆完成后：
>
> ```mermaid theme={null}
> graph TD
>   n87["87"] --> n45["45"]
>   n87 --> n78["78"]
>   n45 --> n9["9"]
>   n45 --> n17["17"]
>   n78 --> n65["65"]
>   n78 --> n53["53"]
> ```

> [accordion] 堆排序：反复取堆顶
>
> **排序过程**：
>
> 1. 建立初始大根堆
> 2. 堆顶（最大值）与堆的最后一个元素交换
> 3. 堆的有效长度减 1，对堆顶执行向下调整
> 4. 重复第 2、3 步，直到堆中只剩一个元素
>
> 接上例，前两趟：
>
> | 趟 | 交换 | 调整后（左侧为堆，右侧为已就位部分） |
> | - | - | - |
> | 1 | 87 与 53 | 78 45 65 9 17 53 ｜ 87 |
> | 2 | 78 与 53 | 65 45 53 9 17 ｜ 78 87 |
>
> **堆的插入与删除**：
>
> * 插入：新元素放到堆尾，再向上调整，$O(\log n)$
>
> * 删除堆顶：堆尾元素放到堆顶，再向下调整，$O(\log n)$
>
> * 在堆中查找某个元素：$O(n)$
>
> > [!TIP]
> >
> > **向下调整的边界**：交换堆顶与堆尾后，堆的有效长度要减 1；调整时不能越过这个边界。

> [accordion] 堆排序的复杂度与考点
>
> | 操作 | 时间复杂度 |
> | - | - |
> | 建立初始堆 | $O(n)$ |
> | 一次向下调整 | $O(\log n)$ |
> | 删除堆顶、插入 | $O(\log n)$ |
> | 堆排序整体 | $O(n\log n)$ |
>
> * **最好、平均、最坏**：均为 $O(n\log n)$
>
> * **空间复杂度**：$O(1)$
>
> * **稳定性**：不稳定
>
> > [!WARNING]
> >
> > **易错**：建堆是 $O(n)$，不是 $O(n\log n)$；堆排序是原地排序，不需要 $O(n)$ 辅助数组。

## 归并排序

> [accordion] 二路归并的思想与合并过程
>
> **基本思想**（分治）：
>
> 1. 把长度为 $n$ 的序列不断二分，直到每个子序列长度为 1
> 2. 把相邻的两个有序子序列合并成一个有序序列
> 3. 反复合并，直到只剩一个序列
>
> **合并两个有序表**：
>
> * 两个指针分别指向两个子序列的起始位置
>
> * 比较指针所指元素，把较小者放入辅助数组，并移动对应指针
>
> * 某个子序列取完后，把另一个子序列的剩余元素直接复制过去
>
> > [!TIP]
> >
> > **稳定性关键**：两个元素关键字相等时，**优先取左边子序列的元素**，相同关键字的相对次序保持不变，归并排序稳定。

> [accordion] 归并趟数与手动模拟
>
> 每趟归并的时间为 $O(n)$，共需 $\lceil \log_2 n \rceil$ 趟，因此总时间为 $O(n\log n)$。
>
> 以 `49 38 65 97 76 13 27` 为例：
>
> | 趟 | 子序列划分 | 本趟结果 |
> | - | - | - |
> | 初始 | 每个元素单独成段 | 49 ｜ 38 ｜ 65 ｜ 97 ｜ 76 ｜ 13 ｜ 27 |
> | 1 | 两两归并 | 38 49 ｜ 65 97 ｜ 13 76 ｜ 27 |
> | 2 | 相邻两段归并 | 38 49 65 97 ｜ 13 27 76 |
> | 3 | 最后两段归并 | 13 27 38 49 65 76 97 |
>
> ```mermaid theme={null}
> graph TD
>   A["49 38 65 97 76 13 27"] --> B["49 38 65 97"]
>   A --> C["76 13 27"]
>   B --> D["49 38"]
>   B --> E["65 97"]
>   C --> F["76 13"]
>   C --> G["27"]
>   D --> H["49"]
>   D --> I["38"]
>   F --> J["76"]
>   F --> K["13"]
> ```

> [accordion] 归并排序的复杂度与特点
>
> | 指标 | 结论 |
> | - | - |
> | 最好、平均、最坏时间 | 均为 $O(n\log n)$ |
> | 空间复杂度 | $O(n)$（辅助数组） |
> | 稳定性 | 稳定 |
>
> * 时间复杂度**始终**为 $O(n\log n)$，不受初始序列影响
>
> * 需要与原序列等长的辅助数组，空间开销较大
>
> * 适合要求**稳定**且能接受额外空间的场景，也是外部排序的基础
>
> > [!WARNING]
> >
> > **易错**：归并排序不是原地排序；它的最坏情况不是 $O(n^2)$。

## 基数排序

> [accordion] 低位优先（LSD）的分配与收集
>
> **基本思想**：不比较关键字大小，而是按关键字的每一位分配、收集，从最低位到最高位依次进行。
>
> **关键概念**：
>
> * **位数 $d$**：关键字有多少位
>
> * **基数 $r$**：每一位可能的取值个数（十进制数 $r=10$）
>
> * **分配**：按当前位的值，把元素放入对应的队列
>
> * **收集**：按队列编号从小到大把元素串起来
>
> > [!WARNING]
> >
> > **前提**：每一趟分配、收集必须**稳定**。否则前面几趟排好的低位次序会被破坏，最终结果错误。

> [accordion] 三趟基数排序的手动模拟
>
> 以 `278 109 063 930 589 184 505 269 008 083` 为例，基数为 10：
>
> | 趟 | 按哪一位 | 收集后序列 |
> | - | - | - |
> | 初始 | — | 278 109 063 930 589 184 505 269 008 083 |
> | 1 | 个位 | 930 063 083 184 505 278 008 109 589 269 |
> | 2 | 十位 | 505 008 109 930 063 269 278 083 184 589 |
> | 3 | 百位 | 008 063 083 109 184 269 278 505 589 930 |
>
> > [!NOTE]
> >
> > 不足 $d$ 位的关键字高位补 0（如 `008`），保证每一趟都按相同的位数处理。

> [accordion] 基数排序的复杂度与适用条件
>
> $$
> T(n) = O\big(d(n+r)\big)
> $$
>
> | 指标 | 结论 |
> | - | - |
> | 时间复杂度 | $O(d(n+r))$ |
> | 空间复杂度 | $O(n+r)$（$r$ 个队列 + $n$ 个结点） |
> | 稳定性 | 稳定 |
>
> * 属于**非比较排序**，不受 $\Omega(n\log n)$ 下界限制
>
> * 时间复杂度与初始序列无关，只取决于 $d$、$n$、$r$
>
> * 适合关键字**位数少、位数统一、基数小**的数据
>
> * 不适合位数很多、位数差异大或浮点数数据
>
> > [!NOTE]
> >
> > 有的教材只统计 $r$ 个队列的辅助空间，把空间复杂度记作 $O(r)$。

## 计数排序（拓展）

> [accordion] 统计、前缀和与回填
>
> **基本思想**：
>
> 1. 统计每个关键字值出现的次数
>
> 2. 对次数做前缀和，得到每个值在有序序列中的最后位置
>
> 3. 从后向前遍历原序列，把元素放到对应位置，并让该位置前移
>
> * **时间复杂度**：$O(n+k)$，$k$ 为关键字值域大小
>
> * **空间复杂度**：$O(n+k)$（结果数组 + 计数数组）
>
> * **稳定性**：按上述“从后向前回填”实现时稳定
>
> * **适用条件**：关键字为整数且值域较小
>
> > [!NOTE]
> >
> > 计数排序不在 408 大纲要求内，作为与基数排序对照的拓展了解即可。

## 内部排序算法的比较

> [accordion] 复杂度与稳定性总表
>
> **时间复杂度**
>
> | 排序算法 | 最好 | 平均 | 最坏 |
> | - | - | - | - |
> | 直接插入 | $O(n)$ | $O(n^2)$ | $O(n^2)$ |
> | 折半插入 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ |
> | 希尔排序 | 与增量有关 | 与增量有关 | 与增量有关 |
> | 冒泡排序 | $O(n)$ | $O(n^2)$ | $O(n^2)$ |
> | 快速排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ |
> | 简单选择 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ |
> | 堆排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ |
> | 归并排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ |
> | 基数排序 | $O(d(n+r))$ | $O(d(n+r))$ | $O(d(n+r))$ |
>
> **空间复杂度与稳定性**
>
> | 排序算法 | 空间复杂度 | 稳定性 |
> | - | - | - |
> | 直接插入 | $O(1)$ | 稳定 |
> | 折半插入 | $O(1)$ | 稳定 |
> | 希尔排序 | $O(1)$ | 不稳定 |
> | 冒泡排序 | $O(1)$ | 稳定 |
> | 快速排序 | 平均 $O(\log n)$ | 不稳定 |
> | 简单选择 | $O(1)$ | 不稳定 |
> | 堆排序 | $O(1)$ | 不稳定 |
> | 归并排序 | $O(n)$ | 稳定 |
> | 基数排序 | $O(n+r)$ | 稳定 |
>
> > [!WARNING]
> >
> > **折半插入的记法**：教材通常把它的时间复杂度统一记为 $O(n^2)$，因为瓶颈在移动次数。若题目只问**比较次数**，则为 $O(n\log n)$，且与初始序列无关。

> [accordion] 稳定性与复杂度的记忆
>
> **稳定**：直接插入、折半插入、冒泡、归并、基数
>
> **不稳定**：希尔、快速、简单选择、堆
>
> > [!TIP]
> >
> > **口诀**：插入冒泡归并基数稳定；希尔快排选择堆不稳定。
>
> 按时间复杂度分层：
>
> * $O(n^2)$：直接插入、折半插入、冒泡、简单选择、希尔（常见最坏）
> * $O(n\log n)$：快速（平均）、堆、归并
> * 线性级：基数 $O(d(n+r))$、计数 $O(n+k)$

> [accordion] 比较排序的时间下界
>
> 基于关键字比较的排序算法，最坏情况至少需要 $\Omega(n\log n)$ 次比较。
>
> * 快速排序、堆排序、归并排序都属于比较排序
>
> * 基数排序、计数排序通过“分配、统计”确定位置，不属于比较排序，因此不受该下界限制
>
> > [!NOTE]
> >
> > **直观理解**：$n$ 个元素有 $n!$ 种排列，每次比较最多把可能性减半，至少需要 $\log_2(n!)=\Theta(n\log n)$ 次比较。

> [accordion] 特殊结论速查
>
> | 问题 | 结论 |
> | - | - |
> | 一趟排序后能确定元素最终位置 | 冒泡、快速、简单选择、堆排序 |
> | 一趟排序后不能确定任何元素最终位置 | 直接插入、折半插入、希尔、归并、基数 |
> | 比较次数与初始序列无关 | 折半插入（比较次数）、简单选择 |
> | 排序趟数受初始序列影响 | 冒泡（可提前结束）、快速（划分越不均衡，递归越深） |
> | 排序趟数固定 | 直接插入、简单选择、堆排序、归并、基数 |
> | 最好情况可达 $O(n)$ | 直接插入、冒泡 |
> | 最坏仍为 $O(n\log n)$ | 堆排序、归并排序 |
> | 空间 $O(n)$ | 归并排序 |
> | 空间 $O(\log n)$ | 快速排序（平均） |
> | 不稳定但最坏 $O(n\log n)$ | 堆排序 |
> | 稳定且 $O(n\log n)$ | 归并排序 |
>
> > [!NOTE]
> >
> > “一趟能确定最终位置”不等于“一趟后序列有序”。快排一趟只确定枢轴，归并一趟可能让整体更有序，但不能确定任何元素的最终位置。

## 内部排序算法的选择

> [accordion] 按题目要求选算法
>
> | 题目要求 | 推荐算法 |
> | - | - |
> | 数据基本有序 | 直接插入排序 |
> | 要求稳定且 $O(n\log n)$ | 归并排序 |
> | 平均性能最好 | 快速排序 |
> | 要求最坏 $O(n\log n)$ 且原地 | 堆排序 |
> | 数据量太大、不能全部装入内存 | 外部排序 |
> | 关键字位数固定、基数小 | 基数排序 |
> | 关键字为小范围整数 | 计数排序（拓展） |
> | 只要求选出前 $k$ 个最大或最小元素 | 堆排序（建堆后取 $k$ 次） |

> [accordion] 几组容易混淆的对比
>
> **快速排序与归并排序**
>
> * 快排：平均最快、辅助空间小、不稳定、最坏 $O(n^2)$
> * 归并：稳定、最坏也有 $O(n\log n)$、需要 $O(n)$ 辅助空间
>
> **快速排序与堆排序**
>
> * 快排：平均 $O(n\log n)$，最坏 $O(n^2)$
> * 堆排序：最坏仍为 $O(n\log n)$，但实际常数较大、不稳定
>
> **冒泡排序与简单选择排序**
>
> * 冒泡：稳定、可提前结束、最好 $O(n)$
> * 简单选择：不稳定、比较次数固定为 $n(n-1)/2$、交换次数少
>
> **直接插入与希尔排序**
>
> * 直接插入：稳定、适合基本有序的数据
> * 希尔：不稳定、通过分组让序列快速接近有序

## 外部排序

> [accordion] 为什么外部排序关注 I/O
>
> * 待排序文件太大，无法一次全部放入内存，需要借助外存
>
> * 排序过程分为两个阶段：
>   1. **生成初始归并段**：分批读入内存，排好序后写回外存
>   2. **多路归并**：把多个有序归并段合并，直到得到一个完整的有序文件
>
> * 总时间约为“内部排序时间 + 外存读写时间 + 内部归并时间”；数据量大时，读写时间占主导
>
> * 主要性能瓶颈是**磁盘 I/O 次数**，而不是关键字比较次数
>
> > [!NOTE]
> >
> > 每趟归并都要把全部数据读入、写出各一次，因此减少归并趟数是外部排序优化的核心。

> [accordion] 多路平衡归并与归并趟数
>
> 每次同时归并 $k$ 个有序段，称为 **$k$ 路归并**。若有 $r$ 个初始归并段，则归并趟数为：
>
> $$
> S = \left\lceil \log_k r \right\rceil
> $$
>
> * 增大 $k$ 可以减少归并趟数，从而减少 I/O
>
> * $k$ 越大，需要的内存缓冲区越多，且从 $k$ 个元素中选最小值的比较开销越大
>
> * 败者树正是为了降低“从 $k$ 路中选最小”的开销
>
> > [!WARNING]
> >
> > **注意**：$k$ 路归并需要 $k$ 个输入缓冲区加 1 个输出缓冲区；$k$ 受内存容量限制，不能无限增大。
>
> **例**：$r=16$，$k=2$ 时 $S=4$；$k=4$ 时 $S=2$。
>
> > [!NOTE]
> >
> > 若文件共 $N$ 个记录，内存工作区可容纳 $m$ 个记录，传统方法生成的初始归并段数为 $r=\lceil N/m \rceil$；置换-选择排序可使平均段长约为 $2m$，从而减少 $r$。

> [accordion] 败者树：快速选出 k 路中的最小值
>
> **作用**：在多路归并中快速确定当前 $k$ 个待选元素中的最小者。
>
> **结构**：
>
> * 叶结点：各归并段当前参与比较的元素
> * 内部结点：记录一次比较中的**败者**
> * 另设一个变量记录**冠军**（当前最小元素）
>
> ```mermaid theme={null}
> graph TD
>   root["根：败者 b3（17）"]
>   A["内部结点：败者 b0（12）"]
>   B["内部结点：败者 b2（25）"]
>   b0["b0：12"]
>   b1["b1：8"]
>   b2["b2：25"]
>   b3["b3：17"]
>   root --> A
>   root --> B
>   A --> b0
>   A --> b1
>   B --> b2
>   B --> b3
> ```
>
> 图中 4 路归并的冠军是 b1（8），单独记录在 `ls[0]` 中；根结点记录的是最后一次比较的败者 b3。
>
> **调整过程**：
>
> 1. 输出冠军所在归并段的下一个元素，替换该叶结点
>
> 2. 从该叶结点向上，与路径上记录的败者比较
>
> 3. 胜者继续向上，败者留在当前结点
>
> 4. 根结点上方得到新的冠军
>
> * 初始化建树：$O(k)$
>
> * 每次输出后调整：$O(\log k)$
>
> > [!TIP]
> >
> > **考点**：败者树解决的是“**如何快速选出最小值**”，它不决定归并段的合并顺序；决定合并顺序、使总 I/O 最小的是**最佳归并树**。

> [accordion] 置换-选择排序：生成长度超过内存的归并段
>
> **目的**：传统方法中，初始归并段长度不超过内存工作区容量 $m$，段数多、归并趟数多。置换-选择排序可以生成长度**大于 $m$** 的归并段。
>
> **过程**：
>
> 1. 把内存工作区装满记录
>
> 2. 选出其中最小者输出，记下刚输出的值 `last`
>
> 3. 从外存读入一条新记录补入工作区
>
> 4. 若新记录不小于 `last`，它可以留在当前归并段；否则**冻结**，留给下一个归并段
>
> 5. 当前归并段无法继续输出时，本段结束；解冻冻结记录，开始生成下一段
>
> > [!TIP]
> >
> > **结论**：随机输入下，置换-选择排序生成的初始归并段平均长度约为 $2m$。
>
> > [!NOTE]
> >
> > **意义**：段数 $r$ 减少，归并趟数 $S=\lceil \log_k r \rceil$ 减少，I/O 次数随之减少。

> [accordion] 最佳归并树：让总 I/O 最小
>
> 各初始归并段长度不同，不同的归并顺序会产生不同的总读写代价。把归并段长度作为叶结点权值，构造 **$k$ 叉哈夫曼树**，即为最佳归并树。
>
> **构造方法**：
>
> 1. 每次选取权值最小的 $k$ 个结点
> 2. 合并成一个新结点，权值为这 $k$ 个结点权值之和
> 3. 把新结点放回，重复直到只剩一个结点
>
> **带权路径长度**：
>
> $$
> WPL = \sum_{i=1}^{n} w_i l_i
> $$
>
> 其中 $w_i$ 为第 $i$ 个归并段的长度，$l_i$ 为该叶结点在归并树中的深度。$WPL$ 越小，总读写次数越少。
>
> **虚段补齐**：$k$ 叉哈夫曼树要求
>
> $$
> (n-1) \bmod (k-1) = 0
> $$
>
> 若不满足，需要补充**权值为 0 的虚段**，补 $k-1-\big((n-1)\bmod(k-1)\big)$ 个（余数不为 0 时）。
>
> > [!WARNING]
> >
> > **注意**：$n$ 是补虚段前的归并段数；补 0 权虚段不增加实际归并代价；2 路归并（$k=2$）时 $k-1=1$，一定整除，不需要补虚段。
>
> **例 1**：$k=3$、$n=8$。$(8-1)\bmod 2=1$，需补 $3-1-1=1$ 个虚段，按 9 个叶结点构造三叉哈夫曼树。
>
> **例 2**：$k=3$，归并段长度为 `2 3 5 7 11`。$(5-1)\bmod 2=0$，无需补虚段。
>
> * 合并 2、3、5，得到 10
> * 合并 7、10、11，得到 28
> * $WPL = 10 + 28 = 38$

## 高频易错点

> [accordion] 结论判断易错清单
>
> | 易错说法 | 正确结论 |
> | - | - |
> | 折半插入排序是 $O(n\log n)$ | 仍为 $O(n^2)$（只减少比较，不减少移动） |
> | 希尔排序稳定 | 不稳定 |
> | 快速排序稳定 | 不稳定 |
> | 简单选择排序稳定 | 不稳定 |
> | 冒泡排序最好情况是 $O(n^2)$ | 设置提前结束标志后为 $O(n)$ |
> | 建堆是 $O(n\log n)$ | 建堆为 $O(n)$ |
> | 堆排序需要 $O(n)$ 辅助空间 | 通常为 $O(1)$ |
> | 归并排序是原地排序 | 通常需要 $O(n)$ 辅助空间 |
> | 归并排序最坏为 $O(n^2)$ | 为 $O(n\log n)$ |
> | 快速排序最坏为 $O(n\log n)$ | 为 $O(n^2)$ |
> | 基数排序依赖关键字比较 | 属于非比较排序 |
> | 败者树用于生成初始归并段 | 败者树用于多路归并选最小值；生成初始归并段用置换-选择排序 |
> | 最佳归并树使用等长归并段 | 按各段长度构造哈夫曼树 |
> | 稳定性与初始序列有关 | 稳定性是算法本身的性质 |

> [accordion] 过程分析易错点
>
> * 直接插入第 $i$ 趟是把 $A[i+1]$ 插入前 $i$ 个元素，注意不要数错趟数
>
> * 冒泡每趟确定的是**当前无序区的最大值**，放在无序区末尾
>
> * 快排一趟只保证枢轴到位，枢轴两侧内部仍可能无序
>
> * 堆排序中交换堆顶与堆尾后，堆的有效长度要减 1，调整时不能越过边界
>
> * 归并排序的手算要按“两两归并”进行，不要跨段随意合并
>
> * 基数排序通常按低位优先（LSD），且每趟稳定
>
> > [!TIP]
> >
> > **检查方法**：手算排序过程时，每一步都问自己“这一步之后，哪些元素的位置已经不会再变了”。

## 考前速记

> [accordion] 一页纸结论
>
> > [!TIP]
> >
> > **稳定性**：稳定——直接插入、折半插入、冒泡、归并、基数；不稳定——希尔、快速、简单选择、堆。
>
> * $O(n^2)$：直接插入、折半插入、冒泡、简单选择、希尔（常见最坏）
> * $O(n\log n)$：快速（平均）、堆、归并
> * 线性级：基数 $O(d(n+r))$、计数 $O(n+k)$
> * 最好 $O(n)$：直接插入、冒泡
> * 最坏仍 $O(n\log n)$：堆、归并
> * 辅助空间 $O(1)$：直接插入、折半插入、希尔、冒泡、简单选择、堆
> * 辅助空间 $O(\log n)$：快速排序（递归栈）
> * 辅助空间 $O(n)$：归并排序；基数排序为 $O(n+r)$

> [accordion] 关键特殊结论
>
> * 折半插入：减少比较，不减少移动
> * 冒泡：一趟确定一个最值的最终位置
> * 快速：一趟划分确定枢轴最终位置
> * 堆：建堆 $O(n)$，整体 $O(n\log n)$
> * 归并：稳定，但需要辅助空间
> * 基数：每一趟必须稳定
> * 外部排序：核心是减少 I/O 次数
> * 败者树：提高多路归并选最小值的效率
> * 最佳归并树：哈夫曼树思想，$WPL$ 最小

> [accordion] 建议重点掌握的题型
>
> 1. **排序过程分析**：给定初始序列，写出每一趟排序后的结果
> 2. **快速排序**：枢轴划分过程、递归过程、最好与最坏情况
> 3. **堆排序**：建堆、删除堆顶、向下调整
> 4. **排序算法比较**：时间复杂度、空间复杂度、稳定性
> 5. **归并排序**：归并过程、归并趟数、辅助空间
> 6. **外部排序**：多路归并、败者树、置换-选择、最佳归并树

> [!TIP]
>
> **下一步**：排序算法的代码实现（快速排序的 `Partition`、堆的向下调整）和手动模拟可以单独整理成专题，与本章的结论表配合复习。


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.