分治算法

分治算法 Divide and Conquer

1. 前提条件

分治是一种算法思想。

它的核心是：把一个大问题拆成多个小问题

小问题解决后

再合并成大问题答案

典型算法：

归并排序
快速排序
二分查找
最近点问题
大整数乘法
矩阵乘法

2. 分治三步

分治固定三步：

1. Divide：分解问题
2. Conquer：解决子问题
3. Combine：合并结果

比如归并排序：

Divide：
把数组分成左右两半

Conquer：
分别排序左右两半

Combine：
合并两个有序数组

3. 分治通用递归模板

void divideConquer(问题范围)
{
if(问题足够小)
{
直接解决;
return;
}

分成若干子问题;

divideConquer(子问题1);
divideConquer(子问题2);

合并子问题答案;

}

4. 例子一：归并排序

归并排序是最标准的分治。

4.1 思想
先分到单个元素

再两两合并

例如：

[5,2,8,1]

分：

[5,2] [8,1]

继续分：

[5] [2] [8] [1]

合并：

[2,5] [1,8]

再合并：

[1,2,5,8]

4.2 代码
#include <stdlib.h>

void merge(int arr[],
int temp[],
int left,
int mid,
int right)
{
int i = left;
int j = mid + 1;
int k = left;

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 = left; p <= right; p++)
{
    arr[p] = temp[p];
}

}
//之前说过这里，其实就是分拆以后隔成两个数组每一项逐项对比之后排序加进来

void mergeSortHelper(int arr[],
int temp[],
int left,
int right)
{
if(left >= right)
{
return;
}

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

mergeSortHelper(arr, temp, left, mid);
mergeSortHelper(arr, temp, mid + 1, right);

merge(arr, temp, left, mid, right);

}

void mergeSort(int arr[], int n)
{
int* temp = malloc(n * sizeof(int));

mergeSortHelper(arr, temp, 0, n - 1);

free(temp);

}
4.3 对应分治三步
Divide：
mid = left + (right-left)/2

Conquer：
mergeSortHelper(left, mid)
mergeSortHelper(mid+1, right)

Combine：
merge(left, mid, right)

5. 例子二：快速排序

快速排序也是分治。

但它和归并排序不同：

归并排序：
先递归，再合并

快速排序：
先分区，再递归

5.1 思想
选一个基准值 pivot。

然后：

比 pivot 小的放左边
比 pivot 大的放右边

pivot 归位后：

左边递归快排
右边递归快排

5.2 代码
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}

int partition(int arr[], int left, int right)
{
int pivot = arr[left];

int i = left;
int j = right;

while(i < j)
{
    while(i < j && arr[j] >= pivot)
    {
        j--;
    }

    while(i < j && arr[i] <= pivot)
    {
        i++;
    }

    if(i < j)
    {
        swap(&arr[i], &arr[j]);
    }
}

arr[left] = arr[i];
arr[i] = pivot;

return i;

}

void quickSort(int arr[], int left, int right)
{
if(left >= right)
{
return;
}

int mid = partition(arr, left, right);

quickSort(arr, left, mid - 1);
quickSort(arr, mid + 1, right);

}

5.3 对应分治三步
Divide：
partition 分区

Conquer：
quickSort(left, mid-1)
quickSort(mid+1, right)

Combine：
不需要额外合并
因为 pivot 已经归位

6. 归并排序 和 快速排序
   归并排序：

先把问题拆到底
再合并答案

重点在 Combine

稳定
需要 O(n) 辅助空间

---

快速排序：

先通过 partition 分好左右
再递归解决左右

重点在 Divide

不稳定
平均 O(nlogn)

7. 分治例子三：二分查找

二分查找也属于分治。

每次把问题规模缩小一半

代码：

int binarySearch(int arr[], int n, int target)
{
int left = 0;
int right = n - 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;

}

对应：

Divide：
用 mid 分成左右

Conquer：
只进入可能的一半

Combine：
不需要合并

8. 分治和动态规划区别

分治：

子问题通常不重叠

例如归并排序：

左半边和右半边互不重叠

动态规划：

子问题大量重叠

例如 Fibonacci：

fib(n-1)
fib(n-2)

会反复算。

所以 DP 需要：

memo / dp数组

分治一般不需要记忆化。

9. 分治易错点

10. 分治不是简单递归。
    它必须有“拆分 + 子问题 + 合并”。

11. 归并排序重点是合并。
    快排重点是分区。

12. 分治子问题一般互不重叠。
    DP 子问题一般会重叠。

13. 递归出口一定要写：
    left >= right

14. mid 推荐写：
    left + (right-left)/2

15. 分治总结
    分治算法

核心思想：
大问题拆成小问题
小问题解决
再合并答案

Divide 分解
Conquer 解决
Combine 合并

典型算法：
归并排序
快速排序
二分查找
最近点问题
矩阵乘法

归并排序：
先递归
后合并

快速排序：
先分区
后递归

分治 vs DP：
分治子问题一般不重叠
DP子问题一般重叠