分治法的基本概念、思想
分治法是一种很重要的算法。 字面解释，分治分治，分而治之。就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 不难发现，分治法的思想与递归极其类似。实际上，分治与递归确实是密不可分。
分治法的策略
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破。 分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模1较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，最后将各子问题的解合并得到原问题的解。
分治法适用的情况
分治法所能解决的问题一般具有以下几个特征：
可分：该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质可治：该问题的规模缩小到一定的程度就可以容易地解决可合并：利用该问题分解出的子问题的解可以合并为该问题的解不重复：该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题
分治法的基本步骤
分治法在每一层递归上都有三个步骤： step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题 step3 合并：将各个子问题的解合并为原问题的解
分治实例 —— 归并排序(MERGE-SORT)
归并排序是利用分治的思想实现的排序方法，该算法采用经典的分治策略，将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案修补在一起，从而完成分而治之。
合并过程图解： 以4、5、7、8、1、2、3、6为例
首先开一个临时的数组temp，然后定义两个指针i、j，分别指向需要合并的一段序列的首元素，然后比较两个指针指向的元素，将较小的那个存入temp数组之中，再将其对应的指针右移。
继续比较两个指针指向的元素，仍然将较小的那个存入temp数组之中，再将其对应的指针右移。
继续比较两个指针指向的元素，还是将较小的那个存入temp数组之中，再将其对应的指针右移。
反复执行以上操作，比较两个指针指向的元素，将较小的那个存入temp数组之中，再将其对应的指针右移。
继续以上步骤
此时7 > 6，故将元素6存入temp数组之中，且j指针无法再往右移动，故将7、8整体移入数组中即可 当temp数组存储完所有元素之后，将其赋值给原数组即可。 比较归并排序与快速排序，会发现归并排序需要开一个额外的数组temp用来存储排好序的元素
归并排序模板
#include
using namespace std;
const int N = 10010;
int num[N];//原数组
int tem[N];//临时数组
void merge(int low,int mid,int high)//合并函数
{
int i = low,j = mid + 1,k = low;//i、j指向需要合并的两个序列的首位置
while (i <= mid && j <= high)//i、j指针都不超过合并序列的最后位置
{
//将较小数存储在temp之中,并且后移指针
if (num[i] < num[j]) tem[k++] = num[i++];
else tem[k++] = num[j++];
}
while (i <= mid) tem[k++] = num[i++];//左半序列还有元素
while (j <= high) tem[k++] = num[j++];//右半序列还有元素
for (int i = low;i <= high;i++) num[i] = tem[i];//拷贝元素
}
void merge_sort(int l,int r)//递归设计:排序函数
{
if (l >= r) return;//递归出口:分解至一个数
int mid = (l + r) / 2;
merge_sort(l,mid);//归并排序左半序列
merge_sort(mid + 1,r);//归并排序右半序列
merge(l,mid,r);//将左右合并
}
int main()
{
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> num[i];
merge_sort(1,n);//对第1个位置到第n个位置进行归并排序
for (int i = 1;i <= n;i++) cout << num[i] << " ";
return 0;
}
分治实例 —— 快速排序
基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
实现原理
设置两个变量 i、j，排序开始时：i = 1，j = n找基准位置，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面，默认序列的第一个数为基准元素，假设为key，先j从右往左试探，直到a[j] < key就停止试探，i从左往右试探，直到a[i] > key就停止试探，如果i < j，就交换a[j]与a[i]；如果i与j相遇，则i或j上的元素与基准元素交换，则这一轮排序结束。此时，基准元素将序列一分为二递归调用分界点前和分界点后的子数组排序，重复2.2、2.3的步骤最终就会得到排序好的数组
例如：6，2，7，3，9，8对这6个数进行从小到大排序
初始时，设数组的第一个元素6为基准，用i指向数组首元素，用j指向数组的最后一个元素，开始扫描。指针j从后往前扫描，直到扫描到一个小于基准6的元素之后，停下。指针i从前往后扫描，直到扫描到一个大于基准6的元素之后，停下。 在达到上图状态的时候，交换元素位置。 j指针继续向左试探，然后指针i、j相遇，此时，交换i、j指向的元素与基准元素的位置.至此，第一趟排序结束。基准6左边的元素均小于6，右边的元素均大于6 对上图中元素6左边的部分进行快速排序。首先指针i指向3，指针j指向2，j先从右往左试探，会发现2 < 3，故直接停下。然后i从左往右试探，发现i、j指针重合。故交换元素位置，如下图。 同理，再对6右边的部分快速排序。首先指针i指向7，指针j指向8，j先从右往左试探，查到比7小的元素，一直走到7的位置停下。发现i、j指针重合。故下一步继续快速排序9、8两个元素。最后得到一个递增序列。
快速排序模板
#include
#include
using namespace std;
const int N = 10010;
int a[N];
int n;
void quick_sort(int l,int r)
{
if (l >= r) return;
int temp = a[l];//保存基准
int i = l,j = r;
while (i != j)
{
while (a[j] >= temp && i < j) j--;//j指针从右往左试探
while (a[i] <= temp && i < j) i++;//i指针从左往右试探
if (i < j) swap(a[i],a[j]);//当i、j指针都停下后,交换元素位置
}
a[l] = a[i];//i == j退出循环,与基准元素交换位置
a[i] = temp;//第一次快排结束,基准元素更新为temp,基准位置更新为i,再继续排序
quick_sort(l,i - 1);//对基准左边快速排序
quick_sort(i + 1,r);//对基准右边快速排序
}
int main()
{
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
quick_sort(1,n);//对第1个元素到第n个元素进行排序
for (int i = 1;i <= n;i++) cout << a[i] << " ";
return 0;
}
快速排序的时间复杂度
最好情况：发生在整个数组被分成两段长度相等的子数组时，为O(nlogn)最坏情况：待排序的序列为正序或者逆序(9、8、7、6、5、4、3…)，每次划分只得到一个比上一次划分少一个记录的子序列，为O(n ^ 2)平均时间复杂度：O(nlogn)