1. 定义

分治算法（Divide and Conquer）是一种将复杂问题分解为若干规模较小但结构相似的子问题，然后递归求解子问题，最后将子问题的解合并成原问题解的算法思想。

分治算法特别适合解决具有以下特性的递归性质问题：

1. 原问题可以分解为若干个规模较小的相同问题。
2. 子问题的解可以合并为原问题的解。
3. 子问题相互独立，即子问题之间没有交集。

---

2. 概述

分治算法通过“分、治、合”三步来解决问题：

• 分解（Divide）：将原问题分解成若干个子问题。
• 解决（Conquer）：递归求解这些子问题，当子问题规模足够小时，直接求解。
• 合并（Combine）：将子问题的解合并成原问题的解。

分治算法常用于排序、查找、计算等问题，并且在许多情况下比简单的迭代算法更高效。

---

3. 算法思想

分治算法的核心思想是将原问题分解为若干规模较小的子问题，递归解决子问题，并将子问题的解合并成原问题的解。具体思想如下：

1. 分解（Divide）：

   • 将大问题分成若干个小问题。通常这些子问题的规模是相似的。
   • 子问题可以独立求解，并且通常是原问题的简化版本。

2. 解决（Conquer）：

   • 对子问题进行递归求解。若子问题规模足够小，则可以直接解决。

3. 合并（Combine）：

   • 将各个子问题的解结合成一个最终解。

---

4. 代码实现

以下是使用分治算法思想实现的归并排序（Merge Sort）的 C++ 示例代码：

归并排序代码（蒟蒻手搓版）

#include<bits/stdc++.h>
using namespace std;
void merge(int arr[],int left,int mid,int right)
{
    int n1=mid-left+1;
	int n2=right-mid;
    int leftArr[1000],rightArr[1000];
    for(int i=0;i<n1;i++) 
    {
        leftArr[i]=arr[left+i];
    }
    for(int i=0;i<n2;i++) 
    {
        rightArr[i]=arr[mid+1+i];
    }
    int i=0,j=0,k=left;
    while(i<n1&&j<n2)
    {
        if(leftArr[i]<=rightArr[j])//merge and sort
        {
            arr[k++]=leftArr[i++];
        }
        else 
        {
            arr[k++]=rightArr[j++];
        }
    }
    while(i<n1) 
    {
        arr[k++]=leftArr[i++];
    }
    while(j<n2) 
    {
        arr[k++]=rightArr[j++];
    }
}
void mergeSort(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);
}
int main()
{
    int arr[]={3,5,1,6,2,9,8};
	int n=7;
	cout<<"old:"<<endl;
    for(int i=0;i<n;i++) 
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    mergeSort(arr,0,n-1);
    cout<<"new:"<<endl;
    for(int i=0;i<n;i++) 
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    return 0;
}

代码解释

1. mergeSort：递归函数，将数组分解为两部分，分别排序后合并。
2. merge：合并两个有序子数组，返回一个整体有序数组。
3. main：主函数，调用 mergeSort 对数组进行排序。

---

5. 例子

合并排序时如何排序：

假设我们有两个已排序的子数组 leftArr 和 rightArr，它们分别表示归并排序过程中分解后的两个有序子数组：

• leftArr = [1, 5]
• rightArr = [2, 6]

我们希望将这两个有序数组合并成一个新的有序数组。

步骤：

1. 初始化指针：

   • 创建一个新的数组 arr[]，用来存放合并后的结果。
   • 设置两个指针 i 和 j，分别指向 leftArr 和 rightArr 的起始位置。还有一个指针 k，指向目标数组 arr[] 的当前位置。

2. 逐个比较：

   • 从 leftArr[i] 和 rightArr[j] 开始比较：
     • 如果 leftArr[i] <= rightArr[j]，则将 leftArr[i] 复制到 arr[k] 中，然后 i++，并且 k++。
     • 如果 leftArr[i] > rightArr[j]，则将 rightArr[j] 复制到 arr[k] 中，然后 j++，并且 k++。

3. 处理剩余元素：

   • 一旦有一个数组中的元素被完全合并到 arr[] 中，剩下的另一个数组中的元素必然是有序的，直接将剩余元素复制到目标数组中。
   • 如果 leftArr 中还有剩余元素，则将剩余元素依次放入 arr[]。
   • 如果 rightArr 中还有剩余元素，则将剩余元素依次放入 arr[]。

举个例子：

假设我们有以下两个有序数组：

• leftArr = [1, 5]
• rightArr = [2, 6]

我们开始合并它们：

1. 初始化：i = 0, j = 0, k = 0

   • 比较 leftArr[i] = 1 和 rightArr[j] = 2：
     • 1 <= 2，所以将 1 放入 arr[k] 中。现在 arr = [1]，i = 1，k = 1。

2. 继续比较：i = 1, j = 0, k = 1

   • 比较 leftArr[i] = 5 和 rightArr[j] = 2：
     • 5 > 2，所以将 2 放入 arr[k] 中。现在 arr = [1, 2]，j = 1，k = 2。

3. 继续比较：i = 1, j = 1, k = 2

   • 比较 leftArr[i] = 5 和 rightArr[j] = 6：
     • 5 <= 6，所以将 5 放入 arr[k] 中。现在 arr = [1, 2, 5]，i = 2，k = 3。

4. 现在 leftArr 中没有剩余元素了，但 rightArr 中还剩下 6，所以将 6 放入 arr[k] 中：

   • arr = [1, 2, 5, 6]，j = 2，k = 4。

结果：

最终合并后的有序数组是 arr = [1, 2, 5, 6]。

---

6. 提醒

1. 递归开销：分治算法通常使用递归实现，在某些情况下可能导致栈空间消耗较大。为了避免过深的递归，可以使用尾递归优化，或者转化为非递归版本。

2. 分解策略的选择：分治的分解策略要根据问题的特性来设计。例如，快速排序选择一个基准元素进行分解，归并排序则直接对数组进行均分。

3. 合并效率：合并步骤的效率直接影响分治算法的整体性能。例如，在归并排序中，合并两个有序子数组的效率是关键，若合并步骤过于复杂或低效，可能会影响算法的表现。

4. 空间复杂度：分治算法常需要额外的空间来存储子问题的解，特别是在归并排序和矩阵乘法等问题中。需要注意内存的管理。

5. 适用场景：分治算法适用于可以分解成独立子问题的问题，如排序、查找、图像处理、矩阵运算等。但并非所有问题都能采用分治方法，有些问题可能更适合动态规划、贪心算法等其他方法。

7.声明

这篇文章为本蒟蒻手搓，但凡有错，请大佬耐心指教

不要忘记点个赞👍！！！