一、如何理解分治算法
分治算法的核心思想就是四个字，分而治之，也就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，然后再合并其结果，就得到原问题的解。
分治算法跟递归有点类似，它们区别是：分治算法是一种处理问题的思想，递归是一种编程技巧。分治算法算法一般合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：
1、分解：将原问题分解成一系列子问题；
2、解决：递归地求解各个子问题，若子问题足够小，则直接求解；
3、合并：将子问题的结果合并成原问题。
分治算法能解决的问题，一般需要满足下面这几个条件：
1、原问题与分解成小问题具有相同的模式；
2、原问题分解成子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别；
3、具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
4、可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。
二、分治算法应用
1、如果编程求出一组数据的有序对个数或者逆序对个数呢？
假设有n个数据，我们期望数据从小到大排列，完全有序的数据的有序度就是 n(n-1)/2，逆序度等于0；相反，倒序排列的数据有序度就是0，逆序度是 n(n-1)/2。除了这两种情况我们就需要用分治算法来计算数据的有序度呀逆序度。
这里我们借用归并排序算法，我们知道在归并算法中，会把两个有序的小数组，合并成一个有序的数组。其实在合并的过程中，就可以计算这两个小数组的逆序对个数。每次合并操作，都计算逆序对个数，把这些计算出来的逆序对个数求和，就是这个逆序对个数了。
实现代码如下：
// 逆序对数量
private int num = 0;
public int count(int[] arr) {
mergeSortCounting(arr, 0, arr.length - 1);
return num;
}
// 并归排序
private void mergeSortCounting(int[] arr, int p, int r) {
if (p >= r) {
return;
}
int q = p + (r - p) / 2;
// 转化成子问题
mergeSortCounting(arr, p, q);
mergeSortCounting(arr, q + 1, r);
// 将子问题的结果合并成原问题
merge(arr, p, q, r);
}
// 合并
private void merge(int[] arr, int p, int q, int r) {
// 新建一个数组来存放 p 到 r的数据
int[] tmp = new int[r - p + 1];
int i = p, j = q + 1, k = 0;
while (i <= q && j <= r) {
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
// 计算A中比B中大的元素个数
num += q - i + 1;
tmp[k++] = arr[j++];
}
}
// 判断哪个子数组还有剩余
int start = i, end = q;
if (j <= r) {
start = j;
end = r;
}
// 将剩余的数据加到tmp中
while (start <= end) {
tmp[k++] = arr[start++];
}
// 将tmp中数据拷贝到arr中
for (i = 0; i < k; i++) {
arr[p + i] = tmp[i];
}
}
2、大规模框架MapReduce中分治思想
如果我们要处理1T、10T、100T 这么大规模的数据，用一台机器处理的效率肯定是非常低的。那我们就把任务拆分到多台机器上来处理，如果拆分之后的小任务之间互不干扰，独立计算，最后再将结果合并。这就是分治思想。
实际上,MapReduce框架只是一个任务调度器，底层依赖GFS来存储数据，依赖Borg管理机器，它从GFS中拿数据，交给Brog中的机器执行，并且时刻监控机器执行的进度，一旦出现机器宕机、进度卡壳等，就重新从Brog中调度一台机器执行。
MapReduce可以处理数据与数据之间存在关系任务，比如，文件中单词出现的频率。也可以处理数据与数据之间没有关系的任务，比如网页分析、分词等，每个网页可以独立的分析、分词，而这两个网页并没有关系。网页几十亿、上百亿，如果单机处理，效率低下，就可以利用MapReduce提供的高可靠、高性能、高容错的并行计算框架，并行的处理这几十亿、上百亿的网页。
总结：两种分治算法的应用场景，一个用来指导编码，降低问题求解的时间复杂度；另一个是解决海量数据处理问题。
