第7章分治算法

🎯 本章学习目标

通过本章的学习，你将能够：

理解分治思想：掌握分治三步曲——分解、解决、合并
区分递归与分治：知道递归是手段、分治是思想
掌握归并排序：熟练掌握归并排序的原理和代码实现
掌握快速排序：理解快速排序的 partition 过程和复杂度
对比两种排序：清楚归并和快排的区别、稳定性、复杂度对比
解决逆序对问题：能用归并排序的合并过程统计逆序对数量
了解快速选择：知道快速选择算法找第 k 大/小元素
理解最大子段和：掌握分治法求最大子段和的三种情况
分析分治复杂度：能用递归式分析分治算法的时间复杂度
应对真题题型：能解决选择、判断、程序阅读、编程等各类分治题目

🗺️ 本章知识图谱

分治算法
├── 基础概念
│   ├── 分治三步曲：分解 → 解决 → 合并
│   ├── 分治 vs 递归：递归是手段，分治是思想
│   └── 子问题须相互独立（否则是DP）
├── 归并排序（Merge Sort）
│   ├── 原理：对半拆分 → 递归排序 → 合并
│   ├── 合并两个有序数组
│   ├── 时间复杂度：O(n log n)
│   ├── 空间复杂度：O(n)
│   ├── 稳定性：✅ 稳定
│   └── 应用：逆序对计数
├── 快速排序（Quick Sort）
│   ├── 原理：选pivot → partition → 递归左右
│   ├── partition 分区过程
│   ├── 平均 O(n log n)，最坏 O(n²)
│   ├── 空间 O(log n)（递归栈）
│   ├── 稳定性：❌ 不稳定
│   ├── pivot 优化：随机选 / 三数取中
│   └── 快速选择（Quick Select）
│       ├── 每次只递归一侧
│       └── 平均 O(n) 找第k大/小
├── 经典应用
│   ├── 逆序对计数（归并排序）
│   ├── 最大子段和（分治：全左/全右/跨中点）
│   └── 二分搜索（分治特例）
└── 复杂度分析
    ├── 递归式 T(n) = aT(n/b) + f(n)
    ├── 归并排序：T(n) = 2T(n/2) + O(n)
    └── 主定理（了解即可）

📖 引言

本章我们进入算法核心思想——分治（Divide and Conquer）。分治是最经典的算法范式之一，归并排序和快速排序都是它的"代表作"，也是 GESP 五级的高频考点。

理解了分治，你就掌握了 O(n log n) 排序的底层逻辑，更能举一反三解决逆序对、第 k 大等经典问题。

一、🧩 分治基本思想

1.1 什么是分治

分治（Divide and Conquer） 的核心就四个字——分而治之：

分解（Divide）：将原问题划分为若干个规模更小、结构相同的子问题
解决（Conquer）：递归地求解各个子问题（子问题足够小时直接求解）
合并（Merge）：将子问题的解组合成原问题的解

1.2 递归与分治的关系

递归是一种编程技巧（函数调用自身）
分治是一种算法思想（问题分解策略）
分治通常用递归实现，但递归不等于分治（如递归求阶乘不是分治）

🔑 关键判断：分治必须满足"子问题相互独立"，如果子问题有重叠依赖，那就是动态规划了。

1.3 分治算法的通用框架

cpp

ReturnType divideConquer(Problem p) {
    if (p is small enough) {
        return solveDirectly(p);   // 基本情况：直接求解
    }
    Problem sub1, sub2, ...;       // 分解
    Result r1 = divideConquer(sub1); // 解决
    Result r2 = divideConquer(sub2);
    // ...
    return merge(r1, r2, ...);     // 合并
}

二、🔀 归并排序（Merge Sort）

2.1 算法原理

归并排序是分治思想的经典体现：

分解：将数组从中间一分为二
解决：递归地对左右两半分别归并排序
合并：将两个已排序的子数组合并为一个有序数组

合并过程使用双指针：每次从两个子数组头部取较小元素放入临时数组，直到某一侧取完，再将另一侧剩余元素直接复制过去。

2.2 完整代码实现

cpp

#include <iostream>
#include <vector>
using namespace std;

// 合并两个有序子数组 arr[l..mid] 和 arr[mid+1..r]
void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) {
    int i = l;       // 左子数组起始位置
    int j = mid + 1; // 右子数组起始位置
    int k = l;       // 临时数组起始位置

    // 双指针：每次取较小的元素
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    // 复制左半剩余元素
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    // 复制右半剩余元素
    while (j <= r) {
        temp[k++] = arr[j++];
    }
    // 将临时数组复制回原数组
    for (int p = l; p <= r; p++) {
        arr[p] = temp[p];
    }
}

// 归并排序递归函数
void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) {
    if (l >= r) return; // 递归终止：只有一个元素

    int mid = l + (r - l) / 2; // 防止溢出的中点计算
    mergeSort(arr, temp, l, mid);       // 排序左半
    mergeSort(arr, temp, mid + 1, r);   // 排序右半
    merge(arr, temp, l, mid, r);        // 合并
}

// 对外接口
void mergeSort(vector<int>& arr) {
    vector<int> temp(arr.size()); // 预分配临时数组
    mergeSort(arr, temp, 0, (int)arr.size() - 1);
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(arr);
    for (int x : arr) cout << x << " ";
    // 输出：3 9 10 27 38 43 82
    return 0;
}

2.3 复杂度分析

时间复杂度 O(n log n)：

设数组长度为 n，归并排序的时间递推式为：

T(n) = 2 \cdot T(n/2) + O(n)

展开推导：

每一层递归有 O(n) 的合并开销
递归深度为 log₂n 层
总时间 = n × log₂n = O(n log n)

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

✅ 归并排序的时间复杂度始终稳定为 O(n log n)，不受数据分布影响。

空间复杂度 O(n)：

合并过程需要一个长度为 n 的临时数组，因此额外空间为 O(n)。递归调用栈深度为 O(log n)，但不是主要空间开销。

2.4 稳定性分析

归并排序是稳定排序 ✅

关键在于合并时的比较条件：if (arr[i] <= arr[j]) —— 当左右元素相等时，优先取左侧元素，保证了相等元素的相对顺序不变。

2.5 经典应用：求逆序对数量

逆序对：在数组中，如果 i < j 且 arr[i] > arr[j]，则 (i, j) 构成一个逆序对。

在归并排序的合并阶段，当 arr[i] > arr[j] 时，左子数组从 i 到 mid 的所有元素都大于 arr[j]，因此可以一次性统计 mid - i + 1 个逆序对。

cpp

#include <iostream>
#include <vector>
using namespace std;

long long mergeCount(vector<int>& arr, vector<int>& temp, int l, int mid, int r) {
    int i = l, j = mid + 1, k = l;
    long long invCount = 0;

    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            // arr[i] > arr[j]：左半从 i 到 mid 的元素都大于 arr[j]
            invCount += (mid - i + 1);
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    for (int p = l; p <= r; p++) arr[p] = temp[p];

    return invCount;
}

long long countInversions(vector<int>& arr, vector<int>& temp, int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    long long count = 0;
    count += countInversions(arr, temp, l, mid);
    count += countInversions(arr, temp, mid + 1, r);
    count += mergeCount(arr, temp, l, mid, r);
    return count;
}

long long countInversions(vector<int>& arr) {
    vector<int> temp(arr.size());
    return countInversions(arr, temp, 0, (int)arr.size() - 1);
}

int main() {
    vector<int> arr = {2, 4, 1, 3, 5};
    // 逆序对：(2,1),(4,1),(4,3)，共3个
    cout << countInversions(arr) << endl; // 输出：3
    return 0;
}

⚠️ 易错点：
逆序对数量可能很大，计数变量必须用 long long
mid 计算应写 l + (r - l) / 2 而非 (l + r) / 2，防止整数溢出
合并时 arr[i] <= arr[j] 用 <= 保证稳定性，统计逆序对时用 > 判断
临时数组可以在外部预分配并传引用，避免每层递归重复创建

三、⚡ 快速排序（Quick Sort）

3.1 算法原理

快速排序同样基于分治思想，但策略与归并排序不同：

分解：选择一个基准元素（pivot），通过分区（partition）将数组分为两部分——小于 pivot 的放左边，大于 pivot 的放右边
解决：递归地对左右两部分快速排序
合并：无需合并！分区后 pivot 已在最终位置，左右子数组天然有序拼接

3.2 分区（Partition）过程

最经典的是 Hoare 分区法（左右指针法）：

选择最右元素为 pivot
左指针从左向右找 ≥ pivot 的元素
右指针从右向左找 ≤ pivot 的元素
交换两者，重复直到指针相遇
最后将 pivot 交换到相遇位置

3.3 完整代码实现

cpp

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

// ==================== 方式1：固定选择最右元素为 pivot ====================
int partitionRight(vector<int>& arr, int l, int r) {
    int pivot = arr[r]; // 选最右元素为基准
    int i = l - 1;      // i 指向小于 pivot 的区域末尾

    for (int j = l; j < r; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[r]); // 将 pivot 放到正确位置
    return i + 1;             // 返回 pivot 的最终位置
}

// ==================== 方式2：随机选择 pivot（推荐） ====================
int partitionRandom(vector<int>& arr, int l, int r) {
    int pivotIdx = l + rand() % (r - l + 1); // 随机选 pivot
    swap(arr[pivotIdx], arr[r]);             // 交换到最右，复用分区逻辑
    return partitionRight(arr, l, r);
}

// ==================== 方式3：三数取中法 ====================
int medianOfThree(vector<int>& arr, int l, int r) {
    int mid = l + (r - l) / 2;
    // 对 arr[l], arr[mid], arr[r] 排序，取中间值
    if (arr[l] > arr[mid]) swap(arr[l], arr[mid]);
    if (arr[l] > arr[r]) swap(arr[l], arr[r]);
    if (arr[mid] > arr[r]) swap(arr[mid], arr[r]);
    swap(arr[mid], arr[r]); // 将中位数放到最右
    return partitionRight(arr, l, r);
}

// 快速排序递归函数
void quickSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;

    int pivotPos = partitionRandom(arr, l, r); // 分区
    quickSort(arr, l, pivotPos - 1);           // 排序左半
    quickSort(arr, pivotPos + 1, r);           // 排序右半
}

void quickSort(vector<int>& arr) {
    srand((unsigned)time(nullptr)); // 设置随机种子
    quickSort(arr, 0, (int)arr.size() - 1);
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    quickSort(arr);
    for (int x : arr) cout << x << " ";
    // 输出：3 9 10 27 38 43 82
    return 0;
}

3.4 复杂度分析

时间复杂度：

情况	时间复杂度	触发条件
最好	O(n log n)	每次分区均匀，pivot 将数组平分
平均	O(n log n)	随机数据 / 随机选择 pivot
最坏	O(n²)	数组已有序且固定选最左/最右为 pivot

最坏情况分析：若每次 pivot 都是最大或最小值，分区极不均衡——一侧为空，另一侧为 n-1 个元素：

T(n) = T(n-1) + O(n) = O(n^2)

🛡️ 避免最坏情况：随机选择 pivot 或三数取中法，使最坏情况几乎不可能发生。

空间复杂度：

平均递归深度 O(log n)，空间 O(log n)
最坏递归深度 O(n)，空间 O(n)
快速排序是原地排序，不需要 O(n) 的额外数组

3.5 稳定性分析

快速排序是不稳定排序 ❌

分区过程中的交换操作可能改变相等元素的相对顺序。例如 [2, 2, 1]，选择最右 1 为 pivot 时，两个 2 的相对位置可能改变。

3.6 经典应用：快速选择第 k 小元素

📚 拓展 · 超纲：快速选择不在五级考纲内（考纲只要求归并排序与快速排序本身）。了解其"每次只递归一侧、平均 O(n)"的思想即可。

利用快速排序的分区思想，每次分区后 pivot 已在正确位置 p：

若 p == k-1，找到答案
若 p > k-1，只递归左半部分
若 p < k-1，只递归右半部分

平均时间复杂度 O(n)（每轮只需处理一侧）。

cpp

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

// 快速选择：返回数组中第 k 小的元素（k 从 1 开始）
int quickSelect(vector<int>& arr, int l, int r, int k) {
    if (l == r) return arr[l];

    int pivotIdx = l + rand() % (r - l + 1);
    swap(arr[pivotIdx], arr[r]);

    // 分区
    int pivot = arr[r];
    int i = l - 1;
    for (int j = l; j < r; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[r]);
    int p = i + 1; // pivot 的位置

    // 根据 pivot 位置决定递归方向
    if (p == k - 1) {
        return arr[p];           // 找到了！
    } else if (p > k - 1) {
        return quickSelect(arr, l, p - 1, k); // 在左半
    } else {
        return quickSelect(arr, p + 1, r, k); // 在右半
    }
}

int findKthSmallest(vector<int>& arr, int k) {
    srand((unsigned)time(nullptr));
    return quickSelect(arr, 0, (int)arr.size() - 1, k);
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    cout << findKthSmallest(arr, 3) << endl;
    // 排序后：3 9 10 27 38 43 82，第3小为10
    return 0;
}

⚠️ 易错点：
分区后 pivot 已经在最终位置，递归时不要包含 pivot（pivotPos-1 和 pivotPos+1）
快速选择只需递归一侧，不是两侧！
第 k 小对应下标 k-1，注意 k 从 1 开始
小规模数据（如 n < 20）可改用插入排序优化常数性能

四、📊 归并排序 vs 快速排序对比

对比维度	归并排序	快速排序
分治策略	先对半拆分，排序后合并	先分区（选pivot），再分别排序
时间复杂度（最好）	O(n log n)	O(n log n)
时间复杂度（平均）	O(n log n)	O(n log n)
时间复杂度（最坏）	O(n log n)	O(n²)
空间复杂度	O(n)（需临时数组）	O(log n)（递归栈，原地排序）
稳定性	✅ 稳定	❌ 不稳定
是否原地排序	❌ 非原地	✅ 原地
合并步骤	需要 O(n) 合并	无需合并
缓存友好性	较差（随机访问临时数组）	较好（原地分区）
适用场景	链表排序、外部排序、逆序对	通用内存排序，实际性能优秀

💡 记忆口诀：归并"先分后合"稳但费空间；快排"先分后治"快但可能不稳。

五、🌐 分治思想综合应用

5.1 最大子段和（分治解法）

问题：给定一个整数数组，找到和最大的连续子数组，返回其最大和。

分治思路：

将数组从中间分为左右两半
最大子段和有三种可能：
- 完全在左半部分 → 递归求解
- 完全在右半部分 → 递归求解
- 跨越中点 → 从中点向左扩展求最大后缀和，向右扩展求最大前缀和，两者相加
取三种情况的最大值

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 求跨越中点的最大子段和
int maxCrossingSum(const vector<int>& arr, int l, int mid, int r) {
    // 从中点向左扩展的最大和
    int leftSum = arr[mid], leftMax = arr[mid];
    for (int i = mid - 1; i >= l; i--) {
        leftSum += arr[i];
        leftMax = max(leftMax, leftSum);
    }
    // 从中点+1向右扩展的最大和
    int rightSum = 0, rightMax = 0;
    if (mid + 1 <= r) {
        rightSum = arr[mid + 1];
        rightMax = arr[mid + 1];
        for (int i = mid + 2; i <= r; i++) {
            rightSum += arr[i];
            rightMax = max(rightMax, rightSum);
        }
    }
    return leftMax + rightMax;
}

int maxSubArraySum(const vector<int>& arr, int l, int r) {
    if (l == r) return arr[l]; // 只有一个元素

    int mid = l + (r - l) / 2;
    int leftMax = maxSubArraySum(arr, l, mid);
    int rightMax = maxSubArraySum(arr, mid + 1, r);
    int crossMax = maxCrossingSum(arr, l, mid, r);

    return max({leftMax, rightMax, crossMax});
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    // 最大子段为 [4,-1,2,1]，和为6
    cout << maxSubArraySum(arr, 0, (int)arr.size() - 1) << endl;
    return 0;
}

复杂度：递推式 $T(n) = 2T(n/2) + O(n)$ ，时间 O(n log n)，空间 O(log n)。

📌 最大子段和还有更优的 O(n) 动态规划解法（Kadane算法），但分治解法是 GESP 常考的分治应用题。

5.2 二分搜索的分治本质

二分搜索虽然简单，但它也是分治思想的体现：

分解：取中间元素 mid，与目标比较
解决：根据比较结果，只在左半或右半继续搜索（子问题规模减半）
合并：无需合并，直接返回结果

cpp

int binarySearch(const vector<int>& arr, int target) {
    int l = 0, r = (int)arr.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) l = mid + 1; // 只需查右半
        else r = mid - 1;                         // 只需查左半
    }
    return -1; // 未找到
}

复杂度： $T(n) = T(n/2) + O(1) = O(\log n)$

🔑 二分搜索是"非典型分治"——每次只处理一个子问题，不需要合并。这也是它与归并/快排的区别。

六、📝 实战练习

练习题 1（编程题）

题目： 题目：使用归并排序将数组 {12, 45, 7, 23, 67, 89, 45, 34, 10} 从小到大排序，输出排序后的结果。

🔑 点击查看答案与解析

参考代码：

cpp

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, vector<int>& temp, int l, int mid, int r) {
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    for (int p = l; p <= r; p++) arr[p] = temp[p];
}

void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(arr, temp, l, mid);
    mergeSort(arr, temp, mid + 1, r);
    merge(arr, temp, l, mid, r);
}

int main() {
    vector<int> arr = {12, 45, 7, 23, 67, 89, 45, 34, 10};
    vector<int> temp(arr.size());
    mergeSort(arr, temp, 0, (int)arr.size() - 1);
    for (int x : arr) cout << x << " ";
    return 0;
}

输出：7 10 12 23 34 45 45 67 89

解析：注意两个 45 的相对顺序保持不变，体现了归并排序的稳定性。

练习题 2（编程题）

题目： 题目：给定数组 {5, 3, 8, 6, 2, 7, 1, 4}，求其中逆序对的总数。

🔑 点击查看答案与解析

参考代码：

cpp

#include <iostream>
#include <vector>
using namespace std;

long long mergeCount(vector<int>& arr, vector<int>& temp, int l, int mid, int r) {
    int i = l, j = mid + 1, k = l;
    long long inv = 0;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            inv += (mid - i + 1);
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    for (int p = l; p <= r; p++) arr[p] = temp[p];
    return inv;
}

long long countInv(vector<int>& arr, vector<int>& temp, int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    long long count = 0;
    count += countInv(arr, temp, l, mid);
    count += countInv(arr, temp, mid + 1, r);
    count += mergeCount(arr, temp, l, mid, r);
    return count;
}

int main() {
    vector<int> arr = {5, 3, 8, 6, 2, 7, 1, 4};
    vector<int> temp(arr.size());
    cout << countInv(arr, temp, 0, (int)arr.size() - 1) << endl;
    return 0;
}

输出：17

解析：手动枚举验证：

5 大于 3,2,1,4 → 4个
3 大于 2,1 → 2个
8 大于 6,2,7,1,4 → 5个
6 大于 2,1,4 → 3个
2 大于 1 → 1个
7 大于 1,4 → 2个
总计 4+2+5+3+1+2 = 17

练习题 3（编程题）

题目： 题目：给定数组 {15, 7, 22, 9, 33, 14, 6, 28}，使用快速选择算法找出第 3 大的元素。

🔑 点击查看答案与解析

参考代码：

cpp

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

int quickSelect(vector<int>& arr, int l, int r, int k) {
    if (l == r) return arr[l];

    int pivotIdx = l + rand() % (r - l + 1);
    swap(arr[pivotIdx], arr[r]);

    int pivot = arr[r];
    int i = l - 1;
    for (int j = l; j < r; j++) {
        if (arr[j] >= pivot) { // 降序分区：大于等于 pivot 的放左边
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[r]);
    int p = i + 1;

    if (p == k - 1) return arr[p];
    else if (p > k - 1) return quickSelect(arr, l, p - 1, k);
    else return quickSelect(arr, p + 1, r, k);
}

int main() {
    srand((unsigned)time(nullptr));
    vector<int> arr = {15, 7, 22, 9, 33, 14, 6, 28};
    // 降序排列：33, 28, 22, 15, 14, 9, 7, 6
    // 第3大为 22
    cout << quickSelect(arr, 0, (int)arr.size() - 1, 3) << endl;
    return 0;
}

输出：22

解析：降序分区时比较条件改为 >=，第 k 大对应下标 k-1。快速选择平均时间复杂度为 O(n)。

练习题 4（判断题）

题目： 所有递归都是分治算法。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 递归是一种编程技巧（函数调用自身），分治是一种算法思想（分解-解决-合并）。分治通常用递归实现，但递归不等于分治。

比如递归求阶乘 fact(n) = n × fact(n-1)，这只是一个简单的递推关系，没有"分解为多个子问题再合并"的过程，所以不是分治。

💡 区分要点：分治必须把问题分成多个独立的子问题，然后合并子问题的解。如果只有一个子问题（如阶乘），那不叫分治。

练习题 5（单选题）

题目： 归并排序的时间复杂度和空间复杂度分别是？（）

A. O(n log n)，O(1)
B. O(n log n)，O(n)
C. O(n²)，O(n)
D. O(log n)，O(1)

🔑 点击查看答案与解析

答案： B

解析：

归并排序：

分解：每次对半分，共 log n 层
合并：每层需要 O(n) 的时间合并
总时间：n × log n = O(n log n)
空间：合并时需要临时数组，O(n)

选 B。

🔥 高频考点：归并排序是稳定排序，快排不是。归并排序需要额外 O(n) 空间，快排只需要 O(log n) 的栈空间。

练习题 6（单选题）

题目： 快速排序在最坏情况下的时间复杂度是？最坏情况发生在什么时候？（）

A. O(n log n)，数组完全随机
B. O(n²)，数组已经有序
C. O(n²)，数组完全随机
D. O(n log n)，数组已经有序

🔑 点击查看答案与解析

答案： B

解析：

快速排序的最坏情况发生在数组已经有序（或完全逆序）时：

如果每次选最左/最右元素当 pivot
那么每次分区后，一边有 n-1 个元素，另一边 0 个
递归树变成一条链，共 n 层
每层需要 O(n) 的比较
总时间 = n × n = O(n²)

优化方法：随机选 pivot 或三数取中，让最坏情况极难出现。

选 B。

💡 记忆技巧：快排怕"有序"——越乱越快，越有序越慢。归并排序不怕，稳定 O(n log n)。

练习题 7（判断题）

题目： 归并排序是稳定排序，快速排序也是稳定排序。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析：

归并排序 ✅ 稳定：合并时如果两个元素相等，优先取左边的，保证相对顺序不变
快速排序 ❌ 不稳定：partition 过程中元素会交换位置，相等元素的相对顺序可能被打乱

💡 什么是稳定排序？如果两个元素值相等，排序后它们的相对位置不变。比如 (A, 3) 和 (B, 3)，A 原来在 B 前面，排序后 A 还在 B 前面，就是稳定的。

练习题 8（单选题）

题目： 数组 [3, 1, 4, 2] 中有多少个逆序对？（逆序对：i < j 且 a[i] > a[j]）（）

A. 2
B. 3
C. 4
D. 5

🔑 点击查看答案与解析

答案： B

解析：

枚举所有 i < j 的组合：

(3, 1) → 3 > 1 ✅ 逆序对
(3, 4) → 3 < 4 ❌
(3, 2) → 3 > 2 ✅ 逆序对
(1, 4) → 1 < 4 ❌
(1, 2) → 1 < 2 ❌
(4, 2) → 4 > 2 ✅ 逆序对

共 3 个逆序对：(3,1), (3,2), (4,2)

选 B。

🔥 归并排序求逆序对：在合并过程中，当右边的元素 arr[j] 小于左边的 arr[i] 时，左边从 i 到 mid 的所有元素都和 arr[j] 构成逆序对，共 mid-i+1 个。

练习题 9（单选题）

题目： 数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 的最大子段和是？（连续子数组的最大和）（）

A. 4
B. 5
C. 6
D. 7

🔑 点击查看答案与解析

答案： C

解析：

最大子段是 [4, -1, 2, 1]，和为 4 + (-1) + 2 + 1 = 6。

分治法求最大子段和的三种情况：

完全在左半边
完全在右半边
跨越中点（从中点往左找最大后缀 + 从中点往右找最大前缀）

三种情况取最大值就是答案。

选 C。

💡 最大子段和也可以用动态规划（O(n)）来做，比分治更高效。但分治的思路更直观，也是分治思想的经典应用。

七、📊 考点总结表

考点	重要程度	出题形式	易错点
分治三步曲（分解-解决-合并）	⭐⭐⭐⭐	选择/判断	和递归的关系搞不清
分治 vs 递归	⭐⭐⭐	选择/判断	递归不等于分治
归并排序原理与实现	⭐⭐⭐⭐⭐	编程题/代码填空	合并过程的边界条件
归并排序复杂度	⭐⭐⭐⭐⭐	选择/判断	时间O(n log n)，空间O(n)
归并排序稳定性	⭐⭐⭐⭐	选择/判断	✅ 稳定，相等时优先取左
快速排序 partition 过程	⭐⭐⭐⭐⭐	程序阅读/代码填空	指针移动顺序和终止条件
快排复杂度	⭐⭐⭐⭐⭐	选择/判断	平均O(n log n)，最坏O(n²)
快排稳定性	⭐⭐⭐⭐	选择/判断	❌ 不稳定
快排最坏情况	⭐⭐⭐⭐	选择	数组已有序时退化到O(n²)
逆序对计数	⭐⭐⭐⭐	编程题/选择	mid-i+1 个逆序对；用long long
快速选择	⭐⭐⭐	选择/程序阅读	平均O(n)找第k大/小
最大子段和（分治）	⭐⭐⭐	选择/编程	三种情况：全左/全右/跨中点

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│         分治算法 · 必背速记卡               │
├─────────────────────────────────────────────┤
│  1. 分治三步曲：分解 → 解决 → 合并         │
│  2. 分治是思想，递归是手段                  │
│  3. 分治要求：子问题相互独立                │
│  4. 归并排序：对半拆 → 递归排 → 合并      │
│  5. 归并排序：时间 O(n log n)，空间 O(n)   │
│  6. 归并排序 ✅ 稳定（相等取左边）         │
│  7. 快速排序：选pivot → 分区 → 递归左右    │
│  8. 快排平均 O(n log n)，最坏 O(n²)        │
│  9. 快排最坏情况：数组已有序（固定pivot）  │
│ 10. 快排 ❌ 不稳定                         │
│ 11. 快排空间 O(log n)（递归栈）            │
│ 12. 逆序对：归并合并时统计，mid-i+1个      │
│ 13. 快速选择：每次只递归一侧，平均 O(n)    │
│ 14. 最大子段和分治：全左/全右/跨中点       │
│ 15. pivot 优化：随机选 / 三数取中          │
└─────────────────────────────────────────────┘

第7章 分治算法 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

📖 引言 ​

一、🧩 分治基本思想 ​

1.1 什么是分治 ​

1.2 递归与分治的关系 ​

1.3 分治算法的通用框架 ​

二、🔀 归并排序（Merge Sort） ​

2.1 算法原理 ​

2.2 完整代码实现 ​

2.3 复杂度分析 ​

2.4 稳定性分析 ​

2.5 经典应用：求逆序对数量 ​

三、⚡ 快速排序（Quick Sort） ​

3.1 算法原理 ​

3.2 分区（Partition）过程 ​

3.3 完整代码实现 ​

3.4 复杂度分析 ​

3.5 稳定性分析 ​

3.6 经典应用：快速选择第 k 小元素 ​

四、📊 归并排序 vs 快速排序对比 ​

五、🌐 分治思想综合应用 ​

5.1 最大子段和（分治解法） ​

5.2 二分搜索的分治本质 ​

六、📝 实战练习 ​

练习题 1（编程题） ​

练习题 2（编程题） ​

练习题 3（编程题） ​

练习题 4（判断题） ​

练习题 5（单选题） ​

练习题 6（单选题） ​

练习题 7（判断题） ​

练习题 8（单选题） ​

练习题 9（单选题） ​

七、📊 考点总结表 ​

⭐ 必背速记卡 ​

第7章分治算法

🎯 本章学习目标

🗺️ 本章知识图谱

📖 引言

一、🧩 分治基本思想

1.1 什么是分治

1.2 递归与分治的关系

1.3 分治算法的通用框架

二、🔀 归并排序（Merge Sort）

2.1 算法原理

2.2 完整代码实现

2.3 复杂度分析

2.4 稳定性分析

2.5 经典应用：求逆序对数量

三、⚡ 快速排序（Quick Sort）

3.1 算法原理

3.2 分区（Partition）过程

3.3 完整代码实现

3.4 复杂度分析

3.5 稳定性分析

3.6 经典应用：快速选择第 k 小元素

四、📊 归并排序 vs 快速排序对比

五、🌐 分治思想综合应用

5.1 最大子段和（分治解法）

5.2 二分搜索的分治本质

六、📝 实战练习

练习题 1（编程题）

练习题 2（编程题）

练习题 3（编程题）

练习题 4（判断题）

练习题 5（单选题）

练习题 6（单选题）

练习题 7（判断题）

练习题 8（单选题）

练习题 9（单选题）

七、📊 考点总结表

⭐ 必背速记卡