# 标准排序算法

> 计算机科学 · CIE A-Level 9618
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u9-standard-sorting-algorithms/

本模块讲解CIE 9618要求的五种标准排序算法，它们的核心特性、时间/空间复杂度和跟踪执行规则。你将学习如何为不同场景比较算法，并解答常见的考试题目。

**先修:** [基础算法跟踪和伪代码](https://www.owlsprep.com/zh/study/cie-9618-u3-algorithm-pseudocode/); [渐近时间和空间复杂度](https://www.owlsprep.com/zh/study/cie-9618-u9-time-space-complexity/)

## 学习目标

- 描述冒泡、插入、选择、归并和快速排序的工作过程
- 对样例输入跟踪每个标准排序算法的执行过程
- 比较不同排序算法的时间、空间和行为特性
- 为给定问题场景选择合适的排序算法

## 简单平方时间排序算法

**简单排序算法** — 一组原地的平方时间排序算法，以实现简单著称，适用于小型或接近有序的数据集，包括冒泡、插入和选择排序。

*例:* 插入排序常被用于更复杂算法中对小型数据集排序

这三种简单算法都会逐步构建输入数组的已排序部分，在原地修改数组以避免额外内存开销。每种算法使用不同的方法来扩展已排序部分。

**例题:** 使用插入排序对数组$[4, 2, 7, 1]$排序，展示所有中间步骤。

1. 初始时将第一个元素作为已排序部分
2. 初始状态：$[4 \mid 2, 7, 1]$
3. 取出下一个未排序元素2，将4右移，把2插入已排序部分
4. 第1步后的状态：$[2, 4 \mid 7, 1]$
5. 取出下一个未排序元素7，它比4大，所以插入到已排序部分末尾
6. 第2步后的状态：$[2, 4, 7 \mid 1]$
7. 取出下一个未排序元素1，将7、4、2依次右移，把1插入到已排序部分开头
8. 最终排序后的数组：$[1, 2, 4, 7]$

> **tip**
>
> 冒泡排序通过反复交换相邻的逆序元素工作，每一轮完整遍历都会把最大的未排序元素冒泡到正确位置。

> **考试提示:** 当题目要求统计冒泡排序的趟数或交换次数时，将每一趟完整遍历未排序区间记为一趟，不要把单次交换记为一趟。

*计算器:* forbidden

## 归并排序：分治排序算法

**归并排序** — 一种稳定的分治排序算法，递归地将输入拆分为两半，分别排序后再将两个有序子数组合并为一个有序数组。

*例:* 归并排序非常适合对链表排序，因为链表的合并操作成本很低

归并排序性能稳定，是处理大型数据集的可靠选择。和快速排序不同，无论输入初始顺序如何，它的时间复杂度都是固定的。

**例题:** 使用归并排序对$[3, 1, 4, 2]$排序，展示拆分和合并步骤。

1. 将原数组拆分为两个相等的半区
2. 拆分结果：$[3, 1]$ 和 $[4, 2]$
3. 将每个半区继续拆分为单元素子数组（天然有序）
4. 拆分结果：$[3], [1], [4], [2]$
5. 合并第一对：比较3和1，得到有序子数组$[1, 3]$
6. 合并第二对：比较4和2，得到有序子数组$[2, 4]$
7. 合并两个有序子数组：依次取出1、2、3、4
8. 最终排序后的数组：$[1, 2, 3, 4]$

> **info**
>
> 标准归并排序不是原地算法，需要$O(n)$额外内存来存储临时合并的子数组。

*计算器:* forbidden

## 快速排序：基于划分的分治排序算法

**快速排序** — 一种原地的分治排序算法，选择一个枢纽元素，将数组划分为小于枢纽和大于枢纽的两部分，然后递归排序两个划分区间。

*例:* 由于平均性能出色，快速排序通常是通用内存内排序的默认算法

枢纽选择对快速排序的性能至关重要。常见的枢纽选择包括第一个元素、最后一个元素、中间元素或随机元素。糟糕的枢纽选择会导致最坏情况的平方时间复杂度。

**例题:** 使用快速排序对$[5, 2, 6, 1, 3]$排序，每一步都选择最后一个元素作为枢纽。

1. 原数组：$[5, 2, 6, 1, 3]$，枢纽 = 3
2. 划分：小于3的元素 = $[2, 1]$，枢纽，大于3的元素 = $[5, 6]$
3. 对左划分区间$[2, 1]$递归，枢纽 = 1
4. 划分：小于1的元素 = $[]$，枢纽 = 1，大于1的元素 = $[2]$，排序完成
5. 合并左划分结果：$[1, 2]$
6. 对右划分区间$[5, 6]$递归，枢纽 = 6，排序结果为$[5, 6]$
7. 合并所有部分：左 + 枢纽 + 右 = $[1, 2, 3, 5, 6]$
8. 最终排序后的数组：$[1, 2, 3, 5, 6]$

> **考试提示:** 跟踪快速排序时，每次选择枢纽后都必须展示划分步骤，大部分分数都在这里。

*计算器:* forbidden

## 排序算法特性比较

在考试中回答比较类问题时，你需要参考四个核心特性：时间复杂度（最好/平均/最坏）、空间复杂度、算法是否原地，以及算法是否稳定。

| 算法 | 最好时间 | 平均时间 | 最坏时间 | 原地？ | 稳定？ |
| --- | --- | --- | --- | --- | --- |
| 冒泡排序 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | 是 | 是 |
| 插入排序 | $O(n)$ | $O(n^2)$ | $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^2)$ | 是 | 否 |

**概念自测**

检测你对核心特性的理解：

1. 哪种算法的最坏情况时间复杂度永远是$O(n \log n)$？

   - 冒泡排序
   - 归并排序
   - 快速排序
   - 插入排序

   *答案:* 归并排序

   *解析:* 正确！归并排序总是将输入拆分为相等的两半，因此无论输入顺序如何，时间复杂度永远是$O(n \log n)$。

2. 以下哪种算法不是原地算法？

   - 快速排序
   - 插入排序
   - 归并排序
   - 选择排序

   *答案:* 归并排序

   *解析:* 正确！标准归并排序需要额外$O(n)$内存来存储临时合并的子数组。

**考试命令词**

本主题常见的考试指令术语：

- **Trace** — 展示算法执行的每一步，包括所有中间数组状态 *(对输入跟踪冒泡排序的2趟排序过程)*

- **Compare** — 说明算法之间的异同点，包括复杂度和特性 *(针对大型数据集比较快速排序和归并排序)*

*计算器:* forbidden

## 常见错误

- **错误做法:** 认为快速排序的时间复杂度永远是$O(n \log n)$
  - 原因: 在有序/逆序输入中选择糟糕的枢纽时，快速排序会退化为$O(n^2)$时间
  - 正确做法: 说明快速排序的平均时间是$O(n \log n)$，最坏情况时间是$O(n^2)$
- **错误做法:** 忘记标准归并排序不是原地算法
  - 原因: 这是考试中常见的题目，考察对算法核心特性的掌握
  - 正确做法: 记住归并排序需要$O(n)$额外内存，因此它不是原地算法
- **错误做法:** 冒泡排序的趟数统计错误
  - 原因: 常见错误是将单次交换记为一趟，导致失分
  - 正确做法: 一趟完整排序会处理所有未排序元素，因此n个元素最多需要n-1趟
- **错误做法:** 认为所有原地排序算法都是稳定的
  - 原因: 稳定性取决于交换的实现方式，和排序是否原地无关
  - 正确做法: 记住选择排序和快速排序是不稳定的，冒泡、插入和归并是稳定的
- **错误做法:** 归并排序中先合并再递归拆分
  - 原因: 很多学生混淆了分治算法的操作顺序
  - 正确做法: 先拆分数组，递归排序每个半区，再合并两个有序半区

## 速查表

| 算法 | 最坏时间 | 原地？ | 稳定？ |
| --- | --- | --- | --- |
| 冒泡 | $n^2$ | Y | Y |
| 插入 | $n^2$ | Y | Y |
| 选择 | $n^2$ | Y | N |
| 归并 | $n \log n$ | N | Y |
| 快速 | $n^2$ | Y | N |

## 下一步

标准排序算法是CIE 9618中所有高级算法设计主题的核心基础。理解它们的复杂度和特性将帮助你为任何问题选择正确的算法，这是试卷2的核心技能。你会在编写排序问题伪代码、分析更复杂算法的效率，以及备考中解决混合搜索排序问题时应用这些知识。

- [标准搜索算法](https://www.owlsprep.com/zh/study/cie-9618-u9-standard-searching-algorithms/)
- [算法跟踪](https://www.owlsprep.com/zh/study/cie-9618-u9-algorithm-tracing/)
- [数据类型与结构](https://www.owlsprep.com/zh/study/cie-9618-u10-overview/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u9-standard-sorting-algorithms/