C++ 分治算法入门教程（通俗易懂，详细讲解）

---

🧠 什么是分治算法？

分治算法（Divide and Conquer） 是一种非常经典的算法思想。它的核心思想是：

“大事化小，小事了之。”

即将一个复杂的问题分成两个或多个相同或相似的子问题，直到最后子问题变得足够简单可以直接解决，然后将子问题的解合并起来得到原问题的解。

---

🔁 分治的基本步骤

1. 分解（Divide）：将原问题分解成若干个规模较小、结构与原问题相同的子问题。
2. 解决（Conquer）：递归地求解各个子问题，当子问题足够小时直接求解。
3. 合并（Combine）：将子问题的解合并为原问题的解。

---

📌 常见应用示例

• 快速排序（Quick Sort）
• 归并排序（Merge Sort）
• 二分查找（Binary Search）
• 求最大子数组和（Maximum Subarray Problem）
• 大整数乘法（Karatsuba Algorithm）

---

✅ 示例一：归并排序（Merge Sort）

🎯 问题描述：

给定一个无序数组，使用归并排序将其从小到大排序。

🧩 思路分析：

• 分解：将数组从中间分为左右两部分
• 解决：递归地对左右两部分排序
• 合并：将两个有序数组合并为一个有序数组

💻 C++代码实现 + 注释：

#include <iostream>
#include <vector>

using namespace std;

// 合并两个有序数组
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1); // 创建临时数组
    int i = left;     // 左边数组指针
    int j = mid + 1;  // 右边数组指针
    int k = 0;        // 临时数组指针

    // 合并两个数组
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 复制左边剩余元素
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    // 复制右边剩余元素
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 将临时数组复制回原数组
    for (int p = 0; p < temp.size(); ++p) {
        arr[left + p] = temp[p];
    }
}

// 归并排序主函数
void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2; // 防止溢出写法

    // 分解
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    // 合并
    merge(arr, left, mid, right);
}

// 打印数组函数
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {6, 5, 3, 1, 8, 7, 2, 4};

    cout << "原始数组: ";
    printArray(arr);

    mergeSort(arr, 0, arr.size() - 1);

    cout << "排序后数组: ";
    printArray(arr);

    return 0;
}

📝 输出结果：

原始数组: 6 5 3 1 8 7 2 4 
排序后数组: 1 2 3 4 5 6 7 8

---

✅ 示例二：快速排序（Quick Sort）

🎯 问题描述：

给定一个无序数组，使用快速排序将其从小到大排序。

🧩 思路分析：

• 分解：选择一个基准值（pivot），将数组划分为两部分，一部分小于等于 pivot，另一部分大于 pivot
• 解决：递归地对左右两部分排序
• 合并不需要额外操作，因为划分已经完成排序

💻 C++代码实现 + 注释：

#include <iostream>
#include <vector>

using namespace std;

// 分区函数：返回基准值最终位置
int partition(vector<int>& arr, int left, int right) {
    int pivot = arr[right]; // 选最右边的元素作为基准
    int i = left - 1;       // i 表示小于 pivot 的区域的最后一个位置

    for (int j = left; j < right; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            swap(arr[i], arr[j]); // 把比 pivot 小的放到前面
        }
    }

    swap(arr[i + 1], arr[right]); // 把 pivot 放到正确位置
    return i + 1;
}

// 快速排序主函数
void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int pi = partition(arr, left, right); // 分解+处理

    // 分别对左右两边排序
    quickSort(arr, left, pi - 1);
    quickSort(arr, pi + 1, right);
}

// 打印数组函数
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {6, 5, 3, 1, 8, 7, 2, 4};

    cout << "原始数组: ";
    printArray(arr);

    quickSort(arr, 0, arr.size() - 1);

    cout << "排序后数组: ";
    printArray(arr);

    return 0;
}

📝 输出结果：

原始数组: 6 5 3 1 8 7 2 4 
排序后数组: 1 2 3 4 5 6 7 8

---

✅ 示例三：二分查找（Binary Search）

🎯 问题描述：

在一个有序数组中查找某个目标值是否存在。

🧩 思路分析：

• 分解：每次比较中间值，缩小查找范围
• 解决：找到目标值或者范围为空
• 合并：不需要，只需返回索引即可

💻 C++代码实现 + 注释：

#include <iostream>
#include <vector>

using namespace std;

// 二分查找函数
int binarySearch(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // 找到目标值
        } else if (arr[mid] < target) {
            left = mid + 1; // 查找右半部分
        } else {
            right = mid - 1; // 查找左半部分
        }
    }

    return -1; // 未找到
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8};
    int target = 5;

    int index = binarySearch(arr, target);

    if (index != -1) {
        cout << "找到目标值，索引为：" << index << endl;
    } else {
        cout << "未找到目标值" << endl;
    }

    return 0;
}

📝 输出结果：

找到目标值，索引为：4

---

📚 总结

算法	时间复杂度	特点
归并排序	O(n log n)	稳定排序，适合链表排序
快速排序	平均 O(n log n)，最坏 O(n²)	不稳定，但实际运行快
二分查找	O(log n)	仅适用于有序数组

---

📝 学习建议

1. 先理解递归的概念
2. 掌握分治的三大步骤：分解、解决、合并
3. 多练习经典题目（如归并排序、快速排序、最大子数组等）
4. 能够画出递归调用树帮助理解执行流程

---

如果你还想学习更多分治算法，比如：

• 求最大子数组和（Kadane's Algorithm 或 分治法）
• 求幂运算（快速幂）
• 大整数乘法（Karatsuba）

欢迎继续提问！我可以为你提供更深入的讲解和完整代码示例 😄