GESP快速排序考点精讲｜真题解析与算法模板
updated 2026-09-05 · qu7.top
GESP 快速排序考点完全攻略
为什么快速排序是 GESP 高频考点？
在 GESP 5-8 级的历年真题中，排序算法几乎每次必考，而 快速排序（Quick Sort） 又是其中的重中之重。
原因很简单：
- 快速排序是 分治思想 的典型代表
- 它涉及 递归、数组操作、边界条件 等 GESP 核心考点
- 时间复杂度分析是 GESP 常考的理论题
一、快速排序的核心原理
基本思想（分治法）
快速排序(arr, left, right):
1. 选择一个基准值（pivot）
2. 将数组分为两部分：左边 ≤ pivot，右边 > pivot
3. 递归排序左半部分
4. 递归排序右半部分
关键步骤：分区（Partition）
分区是快速排序的核心。以常见的 Lomuto 分区方案 为例：
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1; // i 是「小于等于pivot区域」的边界
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]); // 把小于等于pivot的元素放到左边
}
}
swap(arr[i + 1], arr[high]); // 把pivot放到正确位置
return i + 1; // 返回pivot的最终索引
}
完整快速排序模板
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 获取分区点
quickSort(arr, low, pi - 1); // 排序左半部分
quickSort(arr, pi + 1, high); // 排序右半部分
}
}
二、GESP 真题中快速排序的常见考查方式
类型 1：给定初始数组，求某一趟排序后的结果
例题风格：对数组 [49, 38, 65, 97, 76, 13, 27] 进行快速排序，若选取第一个元素 49 作为基准，则 第一趟排序结束后 数组的状态是？
解题技巧：
- 明确基准值（pivot）的选择方式（首元素 / 尾元素 / 中间元素）
- 模拟分区过程，逐步追踪元素位置
- 注意题目要求的分区方案（Lomuto 或 Hoare）
类型 2：快速排序的时间/空间复杂度
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n log n) | 每次分区均匀 |
| 平均情况 | O(n log n) | 随机数据 |
| 最坏情况 | O(n²) | 数组已有序/逆序，且每次选首/尾元素为 pivot |
| 空间复杂度 | O(log n) | 递归调用栈 |
⚠️ GESP 常考陷阱：最坏情况的时间复杂度！很多学生只记住了 O(n log n) 却忘了 O(n²)。
类型 3：快速排序 vs 其他排序算法的比较
GESP 经常考各种排序算法的对比：
| 排序算法 | 最好时间 | 平均时间 | 最坏时间 | 稳定性 | 空间复杂度 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | 稳定 | O(1) |
| 选择排序 | O(n²) | O(n²) | O(n²) | 不稳定 | O(1) |
| 插入排序 | O(n) | O(n²) | O(n²) | 稳定 | O(1) |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | 不稳定 | O(log n) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | 稳定 | O(n) |
类型 4：代码填空 / 补全
GESP 5 级以上可能出现给出不完整的快速排序代码，要求填写关键行。
高频填空点：
if (low < high)这个递归终止条件partition函数中的swap操作- 递归调用时的边界
pi - 1和pi + 1
三、快速排序的 GESP 备考策略
- 理解 > 死记：不要死背代码，要能在纸上手动模拟分区过程
- 注意边界：
low < high还是low <= high？i + 1还是i？这些细节决定正误 - 对比学习：把快速排序和归并排序放在一起学，理解它们的异同
- 真题练习：本站收录的 GESP 4-8 级真题 中包含大量排序相关题目
四、快速排序知识检查清单
备考前，确认你已经掌握了以下内容：
- 能口述快速排序的基本思想和分治策略
- 能手动对一个小数组完成一趟快速排序的分区过程
- 知道最好/平均/最坏时间复杂度及其出现条件
- 了解快速排序为什么不稳定（举例说明）
- 能写出完整的 quickSort + partition 代码
- 知道如何优化最坏情况（随机选择 pivot）
🔥 排序算法是 GESP 的必考点，不要在这个问题上丢分。现在就去 GESP 真题专区 找几套排序相关的试卷练练手！