标准排序算法

计算机科学· Unit 9: Algorithm design & problem solving· 5 分钟阅读

1. 简单平方时间排序算法★★☆☆☆⏱ 20 min

🚫 计算器禁用

📘 定义

简单排序算法

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

例:

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

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

📐 例题

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

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

Exam tip:

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

2. 归并排序：分治排序算法★★★☆☆⏱ 25 min

🚫 计算器禁用

📘 定义

归并排序

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

例:

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

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

📐 例题

使用归并排序对 $[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]$

3. 快速排序：基于划分的分治排序算法★★★★☆⏱ 25 min

🚫 计算器禁用

📘 定义

快速排序

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

例:

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

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

📐 例题

使用快速排序对 $[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]$

Exam tip:

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

4. 排序算法特性比较★★★☆☆⏱ 20 min

🚫 计算器禁用

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

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

✓ 快速检测

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

哪种算法的最坏情况时间复杂度永远是 $O (n lo g n)$ ？
- 冒泡排序
- 归并排序
- 快速排序
- 插入排序
显示答案
1 —
正确！归并排序总是将输入拆分为相等的两半，因此无论输入顺序如何，时间复杂度永远是 $O (n lo g n)$ 。
以下哪种算法不是原地算法？
- 快速排序
- 插入排序
- 归并排序
- 选择排序
显示答案
2 —
正确！标准归并排序需要额外 $O (n)$ 内存来存储临时合并的子数组。

5. 常见陷阱

错误做法:

认为快速排序的时间复杂度永远是 $O (n lo g n)$

原因:

在有序/逆序输入中选择糟糕的枢纽时，快速排序会退化为 $O (n^{2})$ 时间

正确做法:

说明快速排序的平均时间是 $O (n lo g n)$ ，最坏情况时间是 $O (n^{2})$

错误做法:

忘记标准归并排序不是原地算法

原因:

这是考试中常见的题目，考察对算法核心特性的掌握

正确做法:

记住归并排序需要 $O (n)$ 额外内存，因此它不是原地算法

错误做法:

冒泡排序的趟数统计错误

原因:

常见错误是将单次交换记为一趟，导致失分

正确做法:

一趟完整排序会处理所有未排序元素，因此n个元素最多需要n-1趟

错误做法:

认为所有原地排序算法都是稳定的

原因:

稳定性取决于交换的实现方式，和排序是否原地无关

正确做法:

记住选择排序和快速排序是不稳定的，冒泡、插入和归并是稳定的

错误做法:

归并排序中先合并再递归拆分

原因:

很多学生混淆了分治算法的操作顺序

正确做法:

先拆分数组，递归排序每个半区，再合并两个有序半区

6. 速查表

算法	最坏时间	原地？	稳定？
冒泡	$n^{2}$	Y	Y
插入	$n^{2}$	Y	Y
选择	$n^{2}$	Y	N
归并	$n lo g n$	N	Y
快速	$n^{2}$	Y	N

7. 常见问题

9618考试需要我记住哪些排序算法？

CIE 9618要求完整掌握5种标准排序算法：冒泡排序、插入排序、选择排序、归并排序和快速排序。你需要能够跟踪它们的执行过程、比较特性，以及编写/补全它们的伪代码。

考试中我需要记住时间复杂度的值吗？

是的，你需要记住全部5种标准排序算法的最好、平均、最坏情况时间复杂度，空间复杂度以及其他特性。

真题中的出现

AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。

2022 · 2
跟踪冒泡排序对输入的执行过程
2023 · 2
比较快速排序和归并排序的特性
2024 · 2
识别稳定排序算法

深入阅读

syllabusCIE 9618 官方大纲大纲第42页参考内容

下一步

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