竞极 Ace

11 快速排序与归并排序

GESP C++ 五级：快速排序与归并排序

核心目标：理解分治算法的基本原理，掌握快速排序与归并排序的算法思想、标准代码实现与递归调用过程，理解两者的时间复杂度、空间复杂度与稳定性差异，能分析递归调用次数与执行流程，能解决排序综合应用问题。
两者都是分治思想的典型应用——快速排序靠“选基准、分左右、递归排”，平均 O(n log n)、最坏 O(n²)，不稳定、原地排序；归并排序靠“对半分、递归排、合并有序段”，始终 O(n log n)，稳定，但需要 O(n) 额外空间。

一、考纲定位

根据 CCF 官方考纲，五级知识内容明确包含：“分治算法（归并排序和快速排序）” ，考核目标要求“掌握分治算法的基本原理，能够使用归并排序和快速排序对数组进行排序”。

在 GESP 五级考试中，排序算法的考查分布：

考点 重要程度 典型考法
分治算法基本原理 ★★★★★ 选择题
快速排序代码实现 代码填空、程序阅读
归并排序代码实现
时间复杂度分析 选择题高频
稳定性判断
merge() 调用次数 ★★★★☆ 程序阅读
排序综合应用 编程题

二、分治算法基本原理

分治算法（Divide and Conquer）的核心思想是“分而治之”：将一个大问题分解为若干个规模更小的子问题，分别求解子问题，再将子问题的解合并为原问题的解。

分治三步：

  1. 分解（Divide） ：将原问题分解为若干规模更小的子问题。
  2. 解决（Conquer） ：递归地求解各个子问题。
  3. 合并（Combine） ：将子问题的解合并为原问题的解。

分治算法可以不使用递归实现（如迭代版的归并排序），但递归是实现分治最自然的方式。分治算法的时间复杂度不一定是 O(log N)，取决于具体的分解方式和合并代价——快速排序最坏 O(n²)，归并排序始终 O(n log n)。

快速排序和归并排序是分治思想在排序问题上的两大经典应用。

三、快速排序

3.1 核心思想

快速排序的核心流程：

  1. 选基准（pivot） ：从数组中选取一个元素作为基准。
  2. 分区（partition） ：将数组重新排列，使所有小于基准的元素移到基准左边，所有大于基准的元素移到基准右边。
  3. 递归排序：对基准左右两个子数组分别递归执行上述过程。

3.2 标准代码实现（以中间元素为基准）

void quickSort(int a[], int l, int r) {
    if (l >= r) return;                 // 终止条件

    int i = l, j = r;
    int pivot = a[(l + r) / 2];         // 选中间元素为基准

    while (i <= j) {
        while (a[i] < pivot) i++;       // 找左边 >= pivot 的元素
        while (a[j] > pivot) j--;       // 找右边 <= pivot 的元素
        if (i <= j) {
            swap(a[i], a[j]);           // 交换
            i++;
            j--;
        }
    }

    quickSort(a, l, j);                 // 递归排序左半
    quickSort(a, i, r);                 // 递归排序右半
}

3.3 另一种写法：Hoare 分区

int partition(int a[], int low, int high) {
    int pivot = a[low];
    int i = low, j = high;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;   // 从右往左找 < pivot
        while (i < j && a[i] <= pivot) i++;   // 从左往右找 > pivot
        if (i < j) swap(a[i], a[j]);
    }
    swap(a[low], a[i]);
    return i;
}

void quickSort(int a[], int low, int high) {
    if (low >= high) return;
    int mid = partition(a, low, high);
    quickSort(a, low, mid - 1);
    quickSort(a, mid + 1, high);
}

重要注意：在 Hoare 分区中，“从右往左查找”和“从左往右查找”的顺序不能随意交换。必须先执行 while (i < j && a[j] >= pivot) j--，再执行 while (i < j && a[i] <= pivot) i++，这样才能正确完成分区。交换顺序会导致分区逻辑错误。

3.4 时间复杂度

情况 时间复杂度 说明
最好 O(n log n) 每次分区均匀
平均 随机数据
最坏 O(n²) 数组已有序且基准选首/尾元素

最坏情况的来源：当输入数组已经有序（升序或降序）且基准总取首尾元素时，每次分区只能将一个元素放到正确位置，递归深度达到 n，退化为 O(n²)。10⁵ 数据量下操作次数可达 10¹⁰ 量级，远超 1 秒时限。

优化方法：随机化选择基准（如 rand() 选取），可以避免有序数据导致的退化，但不能完全避免最坏情况。

3.5 空间复杂度

O(log n)（递归调用栈），最坏情况下 O(n)。快速排序是原地排序，不需要额外的辅助数组。

3.6 稳定性

快速排序是不稳定的。不论选取哪个元素作为枢轴，远距离跳跃式的交换都有可能打乱原本数值相等的两个元素的先后次序。即使“每次都选取中间元素作为枢轴”，快速排序依然是不稳定的。

四、归并排序

4.1 核心思想

归并排序的核心流程：

  1. 分解：将数组从中间分成左右两个子数组。
  2. 递归：分别对左右两个子数组进行归并排序。
  3. 合并（Merge） ：将两个已排序的子数组合并为一个有序数组。

4.2 标准代码实现

void merge(int a[], int l, int mid, int r) {
    int temp[100005];              // 临时数组
    int i = l, j = mid + 1, k = l;

    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {        // 注意 <= 保证稳定性
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];

    for (int t = l; t <= r; t++) {
        a[t] = temp[t];            // 复制回原数组
    }
}

void mergeSort(int a[], int l, int r) {
    if (l >= r) return;            // 终止条件：只有一个元素
    int mid = (l + r) / 2;
    mergeSort(a, l, mid);          // 递归排序左半
    mergeSort(a, mid + 1, r);      // 递归排序右半
    merge(a, l, mid, r);           // 合并两个有序段
}

4.3 时间复杂度

情况 时间复杂度
最好 O(n log n)
平均
最坏

归并排序的时间复杂度在所有情况下均为 O(n log n)，与输入是否有序无关。因为无论数据如何分布，归并排序都固定地将数组对半分，递归深度始终为 log n。

4.4 空间复杂度

O(n)。归并排序需要额外的辅助数组来暂存合并结果，因此不是原地排序。

4.5 稳定性

归并排序是稳定的。在合并过程中，当 a[i] <= a[j] 时优先取左边的元素，严格控制了相等元素的插入顺序，因此相等元素的相对位置不会改变。

4.6 merge() 函数调用次数

对于长度为 n 的数组，归并排序的 merge() 函数被调用次数为 n - 1 次。

真题示例（2023年12月五级） ：

下面代码用于归并排序，其中 merge() 函数被调用次数为（ ）。
数组 lstA = {1, 3, 2, 7, 11, 5, 3}，长度 7。
答案：C. 6
解析：listA 的长度为 7，根据递归返回的条件 start >= end，merge 函数会被调用 6 次。

五、两种排序算法对比

5.1 核心对比表

对比项 快速排序 归并排序
核心思想 选基准，分区，递归 对半分，递归，合并
时间复杂度（最好） O(n log n) O(n log n)
时间复杂度（平均）
时间复杂度（最坏） O(n²)
空间复杂度 O(log n) O(n)
稳定性 不稳定 稳定
是否原地 ✅ 原地排序 ❌ 需要额外数组
适用场景 内存敏感、平均性能优 要求稳定、最坏性能可控

5.2 稳定性总结

排序算法 稳定性
冒泡排序 稳定
插入排序
归并排序 稳定
选择排序 不稳定
快速排序 不稳定
堆排序 不稳定

记忆口诀：快选希堆不稳定，冒插归基稳定（快速、选择、希尔、堆排序不稳定；冒泡、插入、归并、基数排序稳定）。

5.3 真题辨析

快速排序和归并排序的平均时间复杂度均为 O(n log n)，且都是稳定排序。
答案：错误。快速排序是不稳定排序，归并排序才是稳定排序。

六、GESP五级排序真题精讲

真题1：分治算法判断（样题）

关于分治算法，下列说法错误的是（ ）。
A. 分治算法的核心思想是分而治之，即把问题转化为多个规模更小的子问题求解。
B. 分治算法可以不使用递归实现。
C. 分治算法的时间复杂度是 O(log N)，其中 N 表示问题的规模。
D. 分治算法通常较容易在多核处理器上实现加速。
答案：C
解析：分治算法的时间复杂度不一定是 O(log N)，取决于具体的分解方式和合并代价。快速排序最坏 O(n²)，归并排序 O(n log n)。

真题2：归并排序基本思想（2023年9月）

归并排序算法的基本思想是（ ）。
A. 将数组分成两个子数组，分别排序后再合并。
B. 随机选择一个元素作为枢轴，将数组划分为两个部分。
C. 从数组的...
答案：A

真题3：merge() 调用次数（2023年12月）

下面代码用于归并排序，其中 merge() 函数被调用次数为（ ）。
（数组长度为 7）
答案：C. 6

真题4：快速排序稳定性（2026年3月）

快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。
答案：错误
解析：不论选取哪个元素作为枢轴，远距离跳跃式的交换都有可能打乱原本数值相等的两个元素的先后次序，快速排序本质上是不稳定的。

真题5：快速排序 partition 顺序（2025年9月）

在快速排序的 partition 函数中，while (i < j && arr[j] >= pivot) j-- 和 while (i < j && arr[i] <= pivot) i++ 这两行代码的顺序是否可以交换？
答案：不能交换
解析：必须从右往左先找小于基准值的元素，再从左往右找大于基准值的元素，这样才能正确完成分区。交换顺序会导致分区逻辑错误。

真题6：复杂度判断题（2025年3月）

快速排序算法的时间复杂度与输入是否有序无关，始终稳定为 O(n log n)。
答案：错误
解析：快速排序最坏情况为 O(n²)，当输入有序且基准选首尾元素时会退化。

归并排序算法的时间复杂度与输入是否有序无关，始终稳定为 O(n log n)。
答案：正确。

七、易错点汇总

7.1 快速排序

  1. Hoare 分区中从右往左和从左往右的顺序不能交换，否则分区错误。
  2. 最坏时间复杂度 O(n²)，不是 O(n log n)，有序数据且基准选首尾时退化。
  3. 快速排序不稳定，无论选哪个元素作为枢轴。
  4. 随机化基准不能完全避免最坏情况，只能降低概率。
  5. 递归终止条件 l >= r 不能漏。

7.2 归并排序

  1. merge 中的 <= 保证稳定性：if (a[i] <= a[j]) 取左边，不能写成 <，否则不稳定。
  2. 需要额外 O(n) 空间，不是原地排序。
  3. merge() 调用次数为 n - 1（n 为数组长度）。
  4. 时间复杂度始终 O(n log n)，与数据是否有序无关。
  5. 合并后必须把临时数组复制回原数组。

7.3 通用

  1. 分治算法的时间复杂度不一定是 O(log N)，取决于具体问题。
  2. 快速排序和归并排序都是分治思想的典型应用。
  3. 稳定性判断：快速不稳定，归并稳定，这是高频选择题考点。

八、速查表

需求 快速排序 归并排序
核心操作 选基准分区 对半分合并
递归式 T(n) = T(k) + T(n-k-1) + O(n) T(n) = 2T(n/2) + O(n)
平均时间复杂度 O(n log n) O(n log n)
最坏时间复杂度 O(n²)
空间复杂度 O(log n) O(n)
稳定性 不稳定 稳定
是否原地 是 否
merge/partition 调用次数 约为 n 次 n - 1 次
适用场景 内存敏感 要求稳定
代码关键点 基准选择、分区顺序 <= 保证稳定、复制回原数组

九、总结

快速排序与归并排序是 GESP 五级分治算法的核心内容。

  1. 两者都是分治思想的典型应用：分解 → 递归求解 → 合并。
  2. 快速排序选基准分区，平均 O(n log n)，最坏 O(n²)。
  3. 快速排序不稳定，原地排序，空间 O(log n)。
  4. 归并排序对半分合并，所有情况 O(n log n)。
  5. 归并排序稳定，需要 O(n) 额外空间。
  6. merge() 函数调用次数为 n - 1 次。
  7. Hoare 分区中从右往左查找的顺序不能交换。
  8. 归并排序的 <= 是稳定性的关键。
  9. 分治算法的时间复杂度不一定是 O(log N)。
  10. 多练“稳定性判断”“复杂度判断”“merge 调用次数”“代码填空”四类题。

复习建议：先把两种排序的标准代码写熟，确保闭卷能默写；再重点理解快速排序的最坏情况和归并排序的稳定性；然后练习“merge 调用次数”类程序阅读题；最后结合真题中的判断题和选择题查漏补缺。考试中先判断题目考的是原理、复杂度、稳定性还是代码细节，再套用对应知识作答。