一.原理:
1. 分治算法的基本思想就是:
将一个规模为N的问题分解为K个规模较小的子问题(K <= N)，这些子问题相互独立且与原问题性质相同，求出子问题的解，就可以求出原问题的解。
分治算法是递归的解决问题的一般步骤为：
（1）找出基线条件，这种条件必须尽可能简单
（2）不断将问题分解(或者说缩小规模)，直到符合基线条件。
（3）按原问题的要求，判断子问题的解是否就是原问题的解，或是需要将子问题的解逐层合并构成原问题的解。
一言以蔽之：分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
2.分而治之的重点:
看是否能够发现
重复的子问题，能否发现大问题存在的循环子结构，如果发现就把原问题转化为很简单的小问题。是否能
划分步骤（不同步骤不同解决方法），因为单个步骤往往比整个问题解决起来要简单很多。子问题是否很容易解决，如果子问题都解决不了，那么划分还有啥意义？
比如一个规模为n的问题，可以划分为1和 n-1两个部分，其中1是易于解决的。而n-1这个剩余部分可以用相同的划分方式分成1 , n-2两部分；重复这个过程，最终解决所有问题。
也可以划分成n/2和n/2 两部分，然后对两个部分继续划分，最终都会成为一个1的简单问题。
二.举个🌰 ：
假设你是一个农场主，有一小块土地:
你要将土地均匀分成方块，且分出来的方块要尽可能大。
如何将一块地均匀的分成方块，并确保分出的方块是最大的呢？使用分而治之策略。
- 首先，找出
基线条件，最容易处理的情况，就是一条边的长度是另一条边的整数倍。
如果一边长25m,另一边长50m，那么可使用的最大方块为25m * 25m。换言之，可以将这块地划分成两个这样均匀的方块。
- 找出
递归条件，每次递归调用都必须缩小问题的规模，如何缩小前述问题的规模？我们首先找出这块地可容纳的最大方块。
你可以从这块地划出两个640m * 640m的方块，同时余下一小块640m*400m的地。同时对余下的这块地也使用相同的算法。
最初要划分的土地尺寸为1680m * 640m，而现在要划分的土地更小，为640m * 400m,适用于这小块地的最大方块，也是适用于整块地的最大方块。
再次使用同样的划分方法，对于640m * 400m的土地，可从中划出的最大块地为400m * 400m。
这将余下一块更小的土地，其尺寸为400m * 240m;
再次使用同样的划分方法，你可从这块土地划出最大的方块为240m * 240m，余下一块更小的土地，尺寸为240m * 160m
接下来，从这块土地在划出最大的方块，余下一块更小的土地160m * 80m。
余下的这块土地满足基线条件，因为160是80的整数倍，将这块土地分成两个方块后，将不会再余下任何土地。
因此，对于
最初的那片土地，适用的最大方块是80m * 80m.
三.常见使用:
1. 归并排序:
基本思想:
将待排序元素分成大小大致相同的2个子集合（递归直到最小的排序单元），分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。
基线条件: 当数组为空或只包含一个元素，这种情况下，只需原样返回，不用排序。递归条件:将待排序数组，分成2个子集合，然后将2个子集合，再递归分成只包含一个元素的若干子集合。合并:将若干只有一个元素的数组，两两合并成所要求有两个元素的排序好的子集合，然后逐层往上进行合并。
代码展示:
#include <stdio.h>
//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int *a, int first, int mid, int last) {
int *temp = new int[last];
if (temp == NULL) {
return;
}
int leftStartIndex = first;
int rightStartIndex = mid + 1;
int tmpIndex = 0;
while (leftStartIndex <= mid && rightStartIndex <= last) {
// leftIndex 位置 的值 小于 middleIndex 位置 的值
if (a[leftStartIndex] < a[rightStartIndex]) {
temp[tmpIndex++] = a[leftStartIndex++];
}
// leftIndex 位置 的值 大于 middleIndex 位置 的值
else {
temp[tmpIndex ++] = a[rightStartIndex++];
}
}
while (leftStartIndex <= mid) {
temp[tmpIndex ++] = a[leftStartIndex++];
}
while (rightStartIndex <= last) {
temp[tmpIndex++] = a[rightStartIndex++];
}
for (int i = 0; i < tmpIndex; i ++) {
a[first + i] = temp[i];
}
}
// 归并 排序
void mergesort (int *a, int first, int last) {
if (first < last) {
int middle = (first + last) / 2;
mergesort(a, first, middle);
mergesort(a, middle + 1, last);
mergearray(a, first, middle, last);
}
}
int main(int argc, const char * argv[]) {
// insert code here...
int a[5] = {1, 6, 9, 4, 2};
mergesort(a, 0, 5);
for (int i = 0; i < 5; i++) {
printf("%d ", a[i]);
}
return 0;
}
2.快速排序:
基本思想:
在
待排序的序列中选取一个值作为一个基准值按照这个
基准值的大小将这个序列划分成两个子序列：小于基准值的元素和大于基准值的元素，基准值会在这两个子序列的中间，这样快速排序第一次排完。然后再对
这两个子序列按照同样的方法进行排序，直到只剩下一个元素或者没有元素的时候就停止，这时候所有的元素都出现在了该出现的位置上。基线条件: 当数组为空或只包含一个元素，这种情况下，只需原样返回，不用排序。递归条件:选取一个基准值，将数组分成两个子数组:小于基准值的元素和大于基准值的元素，然后对这两个子数组按照同样方法排序，直到只剩下一个元素或是没有元素的时候停止。合并:将排序后的子数组合并得到的就是所要求的有序数组。
代码展示:
// 快速 排序
void qiuckSort(int *a, int first, int last) {
if (a == NULL) {
return;
}
if (first >= last) {
return;
}
int leftIndex = first;
int rightIndex = last - 1;
int compareValue = a[first];
// 遍历
while (leftIndex < rightIndex) {
// 从后往前 遍历 如果 当前值 大于 基准值
while (leftIndex < rightIndex && a[rightIndex] >= compareValue) {
rightIndex--;
}
a[leftIndex] = a[rightIndex];
// 从前往后遍历 如果当前值 小于 基准值
while (leftIndex < rightIndex && a[leftIndex] <= compareValue) {
leftIndex++;
}
a[rightIndex] = a[leftIndex];
}
a[leftIndex] = compareValue;
qiuckSort(a, first, leftIndex);
qiuckSort(a, leftIndex + 1, last);
}
int main(int argc, const char * argv[]) {
// insert code here...
int a[5] = {1, 6, 9, 4, 2};
qiuckSort(a, 0, 5);
for (int i = 0; i < 5; i++) {
printf("%d ", a[i]);
}
return 0;
}
