排序算法及其算法分析
课程：信息技术导论 — 补充：排序算法及其算法分析 讲师：北京大学 苏清元（推测） 来源：田浩然上传的资料 / 0A006 信息技术导论 格式：PowerPoint 97-2003 二进制格式，47页 提取方式：LibreOffice 转 PDF → pdftotext 全文提取（778行，内容完整）
一、排序基本概念
1.1 为什么要排序？
- 有序表的优点：查找效率高（二分查找 O(log n) vs 顺序查找 O(n)）、便于统计分析、数据组织更清晰
- 有序表的缺点：排序本身需要时间开销、插入删除需要维护有序性
- 排序的本质：构造数据元素之间的次序关系
1.2 核心定义
| 概念 | 定义 |
|---|---|
| 排序（Sorting） | 把一组记录按照某个（或某几个）字段的值，以递增或递减的次序重新排列的过程 |
| 排序码 | 作为比较基础的字段，可以是数值、符号或字符串。排序码不一定唯一 |
| 关键码 | 唯一标识一条记录的字段。关键码可以作为排序码，但排序码不一定是关键码 |
| 稳定性 | 若排序码相同的记录经过排序后前后次序保持不变，则排序方法是稳定的，否则是不稳定的 |
| 内排序 vs 外排序 | 全部记录放在内存 → 内排序；需使用外存 → 外排序 |
1.3 排序方法分类（五大类）
排序算法
├── 插入排序（Insertion）
│ ├── 直接插入排序
│ ├── 二分插入排序
│ ├── 表插入排序
│ └── Shell 排序（缩小增量排序）
├── 选择排序（Selection）
│ ├── 直接选择排序
│ └── 堆排序
├── 交换排序（Exchange）
│ ├── 起泡排序（冒泡排序）
│ └── 快速排序（本PPT未展开）
├── 分配排序（Distribution）
│ └── 基数排序（本PPT未展开）
└── 归并排序（Merge）
└── 二路归并排序（本PPT未展开）
注：本 PPT 详细展开了插入排序（4种）、选择排序（2种）、起泡排序。快速排序、归并排序、分配排序仅列在分类中未展开。
1.4 排序算法评价标准
三大评价维度：
- 时间开销（最重要）：比较次数 + 移动次数
- 最坏情况、最好情况、平均情况
- 空间开销：附加存储单元
- 算法复杂度：实现难度、代码可读性
二、插入排序（Insertion Sort）
核心思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的子序列的合适位置，直到全部插入排序完为止。
2.1 直接插入排序
基本思想：
- 假定前面 m 个元素已经排序
- 取第 (m+1) 个元素，从后向前扫描，插入到前面的适当位置
- 初始 m = 1，重复直到 m = n
示例：{23, 11, 55, 97, 19, 80}
第1趟：{23} → {11, 23}
第2趟：{11, 23} → {11, 23, 55}
第3趟：{11, 23, 55} → {11, 23, 55, 97}
第4趟：{11, 23, 55, 97} → {11, 19, 23, 55, 97}
第5趟：{11, 19, 23, 55, 97} → {11, 19, 23, 55, 80, 97}
性能分析：
| 指标 | 最好情况（正序） | 最坏情况（逆序） | 平均 |
|---|---|---|---|
| 比较次数 | n - 1 ≈ n | n(n-1)/2 ≈ n²/2 | O(n²) |
| 移动次数 | n - 1 ≈ n | n²/2 | O(n²) |
| 时间复杂度 | O(n) | O(n²) | O(n²) |
- 稳定性：✅ 稳定（从后向前找，相等时不交换）
- 空间复杂度：O(1)（仅一个 temp 辅助单元）
2.2 二分法插入排序
改进思路：在直接插入排序的基础上，用二分法代替顺序查找来确定插入位置，减少比较次数。
核心操作：
- 查找插入位置时用二分查找（low/high/mid）
- 找到位置后，移动次数与直接插入排序相同
- 循环结束条件：high < low，插入位置为 low（或 high + 1）
性能分析：
- 比较次数：大大减少，约 O(n log₂ n) 次比较
- 移动次数：与直接插入排序相同，O(n²)
- 时间复杂度：平均 T(n) = O(n²)
- 稳定性：✅ 稳定（比较时使用 temp.key < record[mid].key，相等时向右插入，保持原序）
结论：二分法插入排序只是减少了比较次数，移动次数仍是 O(n²)，因此整体仍是 O(n²)。对比较成本高、移动成本低的场景更有价值。
2.3 表插入排序
改进思路：用链表存储记录，插入时不需要移动记录，只需修改指针。
数据结构：
struct Node {
KeyType key; // 排序码字段
DataType info; // 其他字段
ListNode *next; // 指针字段
};基本方法：
- 记录用链表连接
- 插入 Ri 时，R₀ 至 R_{i-1} 已排序
- 顺序比较找到 Ri 应插入的位置
- 修改指针完成插入（记录本身不移动）
性能分析：
- 比较次数：最多 n(n-1)/2，最少 n-1 → O(n²)
- 移动次数：0（零移动，只改指针）
- 时间效率：O(n²)
- 辅助空间：O(n)（每个记录多一个指针）
- 稳定性：✅ 稳定（p->key <= now->key 保证稳定）
适用场景：记录体积大、移动成本高的排序场景。
2.4 Shell 排序（希尔排序 / 缩小增量法）
提出者：D.L. Shell，1959 年
改进出发点（两个观察）：
- 直接插入排序在初始序列基本有序时效率极高（接近 O(n)）
- 当 n 较小时，n² 的影响不大
核心思想：
- 先取一个增量 d₁ < n，把全部记录分成 d₁ 个组
- 所有距离为 d₁ 倍数的记录放在一组，各组内分别排序
- 然后取 d₂ = d₁ / k，重复分组和排序
- 直到 dᵢ = 1，所有记录放在一组中完成排序
- 各组内排序通常使用直接插入排序
示例：{49, 38, 65, 97, 13, 76, 27, 49’}
原始序列： 49 38 65 97 13 76 27 49'
d=4 分组： 组1: 49, 13, 27
组2: 38, 76, 49'
组3: 65
组4: 97
d=4排序后：13 38 27 49' 49 76 65 97
d=2 分组： 组1: 13, 27, 49, 65
组2: 38, 49', 76, 97
d=2排序后：13 38 27 49' 49 76 65 97
d=1 整体排序（直接插入）
最终结果： 13 27 38 49' 49 65 76 97
增量序列的选取：
- Shell 原始取法：d₁ = ⌊n/2⌋，d_{i+1} = ⌊dᵢ/2⌋
- Knuth 建议：d_{i+1} = ⌊(dᵢ - 1)/3⌋
- 经验法则：增量取奇数、增量之间互素效果较好
- 理论上最优增量序列至今仍未完全解决
性能分析：
- 时间复杂度：约 O(n^1.3)（平均情况），优于 O(n²)
- 空间复杂度：O(1)
- 稳定性：❌ 不稳定（分组排序可能打乱相同排序码记录的相对顺序）
特点：Shell 排序是对直接插入排序的重要改进，通过”先宏观有序，再微观有序”的思路突破了 O(n²) 瓶颈。
三、选择排序（Selection Sort）
核心思想：每趟从待排序的记录序列中选择关键字最小的记录，放置到已排序表的最前位置，直到全部排完。
3.1 直接选择排序
方法：
- 在所有记录中选出排序码最小的，与第一个记录交换
- 在其余记录中再选出最小的，与第二个记录交换
- 以此类推，直到所有记录排好序
性能分析：
- 比较次数：与初始状态无关，始终是 n(n-1)/2 ≈ n²/2
- 第 i 趟需要 n-i 次比较
- 总比较次数 = Σ(n-i) = n(n-1)/2
- 移动次数：
- 最少 Mmin = 0（正序时）
- 最多 Mmax = 3(n-1)（逆序时，每趟 1 次交换 = 3 次移动）
- 时间复杂度：O(n²)
- 辅助空间：O(1)（一个 temp）
- 稳定性：❌ 不稳定（跨位置交换可能改变同值记录次序）
3.2 堆排序（Heap Sort）
堆的定义
n 个排序码序列 K = {k₀, k₁, …, k_{n-1}}，当且仅当满足以下条件时称为堆：
- 大根堆：kᵢ ≥ k_{2i+1} 且 kᵢ ≥ k_{2i+2} （i = 0, 1, …, n/2-1）
- 小根堆：kᵢ ≤ k_{2i+1} 且 kᵢ ≤ k_{2i+2}
几何意义：若将序列看成完全二叉树，堆意味着每个非叶结点的排序码均 ≥（或 ≤）其左右子女结点的排序码。根结点是最大值（大根堆）或最小值（小根堆）。
堆排序主要思想（大根堆为例）
- 将原始序列构造成一个堆 → 最大值在根结点（位置0）
- 交换根结点（最大值）与最后一个元素 → 选到一个最大元素
- 把前 n-1 个元素重新调整为新堆 → 得到第二大元素
- 重复以上操作，直到整个序列有序
两个关键问题
问题一：如何建初始堆？
- 完全二叉树中，⌊n/2⌋, ⌊n/2⌋+1, …, n-1 都是叶子，以它们为根的子树自然是堆
- 只需从第 ⌊n/2⌋-1 个非叶结点开始，从下向上，将每个非叶结点为根的子树调整为堆
- 调整方法：筛选法（shift 函数）
- 假设 Ri 的左右子树都是堆
- 将 Ri 与左右子树根中较大者比较，若 Ri 小则交换
- 若交换破坏了子树的堆特性，则继续向下调整，直到子树成为堆
问题二：丢掉最大值后如何重建堆？
- 同样使用筛选法，对根结点进行一次向下调整
- 时间复杂度 O(log n)
性能分析
| 指标 | 数值 |
|---|---|
| 建初始堆比较次数 | O(n) |
| 重建堆总比较次数 | O(n log₂ n) |
| 总时间复杂度 | O(n log₂ n) |
| 空间复杂度 | O(1) |
| 稳定性 | ❌ 不稳定 |
特点：堆排序时间复杂度稳定为 O(n log₂ n)，最坏情况也不退化，适合 n 较大的场景。空间效率高，原地排序。
四、交换排序（Exchange Sort）
核心方法：两两比较待排序记录的排序码，交换不满足顺序要求的偶对，直到全部满足为止。
4.1 起泡排序（冒泡排序）
方法步骤：
- R₀ 与 R₁ 比较，若前者大则交换
- R₁ 与 R₂ 比较，同上
- 依次类推，直到 R_{n-2} 与 R_{n-1}
- 以上为一趟起泡，最大值”冒”到最后位置
- 对前 n-1 个元素重复上述过程
- 最多 n-1 趟起泡完成排序
- 优化：设 noswap 标志，某趟无交换则已排好序，提前终止
示例：{49, 38, 65, 97, 76, 13, 27, 49’}
第1趟：38 49 65 76 13 27 49' [97]
第2趟：38 49 65 13 27 49' [76 97]
第3趟：38 49 13 27 49' [65 76 97]
第4趟：38 13 27 49' [49 65 76 97]
第5趟：13 27 38 [49' 49 65 76 97]
第6趟：13 27 [38 49' 49 65 76 97]
结果： 13 27 38 49' 49 65 76 97
性能分析：
| 指标 | 最好（正序） | 最坏（逆序） | 平均 |
|---|---|---|---|
| 比较次数 | n - 1 | n(n-1)/2 | O(n²) |
| 移动次数 | 0 | 3n(n-1)/2 | O(n²) |
| 时间复杂度 | O(n) | O(n²) | O(n²) |
- 稳定性：✅ 稳定（相邻比较，相等不交换）
- 空间复杂度：O(1)
五、排序算法对比总表
| 排序方法 | 最好时间 | 最坏时间 | 平均时间 | 空间 | 稳定性 | 特点 |
|---|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n²) | O(n²) | O(1) | ✅ 稳定 | 简单，n小或基本有序时好 |
| 二分插入排序 | O(n log n) 比较 | O(n²) 移动 | O(n²) | O(1) | ✅ 稳定 | 减少比较，移动不变 |
| 表插入排序 | O(n²) | O(n²) | O(n²) | O(n) | ✅ 稳定 | 零移动，适合大记录 |
| Shell 排序 | — | — | O(n^1.3) | O(1) | ❌ 不稳定 | 突破 O(n²)，增量选取很关键 |
| 直接选择排序 | O(n²) | O(n²) | O(n²) | O(1) | ❌ 不稳定 | 比较次数固定，移动少 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ 不稳定 | 最坏不退化，适合n大 |
| 起泡排序 | O(n) | O(n²) | O(n²) | O(1) | ✅ 稳定 | 简单，可提前终止 |
六、关键洞见与关联
6.1 排序算法的层次
O(n) ~ O(n²) 级 简单排序：插入/选择/交换
↓
O(n log n) 级 改进排序：堆排序/快速排序/归并排序
↓
O(n) 级 线性排序：基数排序/计数排序/桶排序（需特定条件）
6.2 排序算法选择的考量
- n 很小（n < 50）：直接插入排序或简单选择排序，代码简单开销小
- n 中等：Shell 排序是不错的选择，实现不算太复杂但效率更好
- n 很大：堆排序/快速排序/归并排序（O(n log n) 级）
- 需要稳定性：插入排序 / 起泡排序 / 归并排序 / 基数排序
- 内存受限：堆排序（原地 O(1) 额外空间）
- 基本有序的数据：直接插入排序效率最高（接近 O(n)）
6.3 与其他知识的关联
- 与 第06章-数据的组织结构与算法-信息技术导论 中的排序章节内容互补，本 PPT 更深入算法细节和复杂度分析
- 堆排序涉及完全二叉树和堆数据结构，与 第06章-数据的组织结构与算法-信息技术导论 中二叉树部分关联
- 快速排序（本 PPT 未展开）使用分治策略，与算法设计课程中的分治法关联
- Shell 排序是”增量式改进”思路的典型：通过分组让数据先大致有序，最后整体排序时效率大大提高
本笔记基于《补充：排序算法及其算法分析.ppt》整理，北京大学信息技术导论课程补充材料，47页，涵盖插入排序4种+选择排序2种+起泡排序共7种排序算法的原理、示例、复杂度分析和稳定性判断。