分治算法
一、算法思想
分治法作为一种常见的算法思想，其概念为：把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，子问题的解的合并即是原问题的解。举个例子，要算16个数的和可能一下子算不出来的，但是可以通过几次一分为二（拆分），直到分成两个数、两个数一组；再对这些数两两相加，算出每组的和后，再两两相加，直到最后只剩下了一个数，就算出16个数的和（合治）。
把一个任务，分成形式和原任务相同，但规模更小的几个部分任务（通常是两个部分），分别完成，或只需要选一部分完成。然后再处理完成后的这一个或几个部分的结果，实现整个任务的完成。1.1 适用场景
可以用分治法解决的问题一般有如下特征：
1>问题的规模缩小到一定的程度就可以容易地解决。此特征是大多数问题所具备的，当问题规模增大时，解决问题的复杂度不可避免地会增加。
2>问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。此特征也较为常见，是应用分治法的前提。
3>拆分出来的子问题的解，可以合并为该问题的解。这个特征在是否采用分治法的问题上往往具有决定性作用，比如棋盘覆盖、汉诺塔等，需要将子问题的解汇总，才是最终问题的解。
4>拆分出来的各个子问题是相互独立的，即子问题之间不包含公共的子问题。该特征涉及到分治法的效率，如果各子问题是不独立的，则需要重复地解公共的子问题，此时用动态规划法更好。
1.2 使用步骤
使用分治法的基本步骤：
1>分解，将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
2>解决，若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。
3>合并，将各个子问题的解合并为原问题的解。
二、分治的生活实例 --称假币
16硬币，有可能有1枚假币，假币比真币轻。有一架天平，用最少称量次数确定有没有假币，若有的话，假币是哪一枚？ 题解： 8 – 8 一称，发现无假币，或假币所在的那8枚 4 – 4 一称 2 – 2 一称 1 – 1 一称三、分治的典型应用：归并排序
数组排序任务可以如下完成： 1） 把前一半排序 2) 把后一半排序 3) 把两半归并到一个新的有序数组，然后再拷贝回原数组，排序完成#include <iostream>
using namespace std;
void Merge(int a[], int s, int m, int e, int tmp[])
{
//将数组a的局部a[s,m]和a[m+1,e]合并到tmp,并保证tmp有序，然后再拷贝回a[s,m]
//归并操作时间复杂度：O（e-m+1),即O（n)
int pb = 0;
int p1 = s, p2 = m + 1;
while (p1 <= m && p2 <= e) {
if (a[p1] < a[p2])
tmp[pb++] = a[p1++];
else
tmp[pb++] = a[p2++];
}
while (p1 <= m)
tmp[pb++] = a[p1++];
while (p2 <= e)
tmp[pb++] = a[p2++];
for (int i = 0; i < e - s + 1; ++i)
a[s + i] = tmp[i];
}
void MergeSort(int a[], int s, int e, int tmp[]) // 归并排序的时间复杂度O(nlogn)
{
if (s < e) {
int m = s + (e - s) / 2;
MergeSort(a, s, m, tmp);
MergeSort(a, m + 1, e, tmp);
Merge(a, s, m, e, tmp);
}
}
int a[10] = { 13,27,19,2,8,12,2,8,30,89 };
int b[10];
int main()
{
int size = sizeof(a) / sizeof(int);
MergeSort(a, 0, size - 1, b);
for (int i = 0; i < size; ++i)
cout << a[i] << ",";
cout << endl;
return 0;
}