分治法（Divide and Conquer）是把一个规模为n的问题分成两个或多个较小的与原问题类型相同的子问题，分而治之，通过对子问题的求解，将子问题的解合并起来从而构造出整个问题的解。如果子问题的规模仍然相当大，可以对子问题重复应用分治策略。分治策略把问题分成若干个子问题，分成的子问题的数目一般不大。如果每次分成的各子问题的规模相等或者近乎相等，则分治效率较高，否则较低。例如：直接插入排序可以看作把原问题分成两个子问题，一个是规模为1的问题，另一个是规模为n-1的问题，算法时间复杂度O(n^2)；而归并排序把原问题分成两个大小为n/2的问题，算法的时间复杂度为O(nlog2n)级。
算法框架
分治策略是将问题分成较小的与原问题同类型的子问题，对子问题的处理过程与对原问题的处理过程相同。所以分治发处理问题的算法可以自然地写成一个递归过程。
一个用分治法编写的过程通常包括基值处理部分（把问题分到足够小后要进行的处理），分解问题的部分，递归调用部分和合并处理部分。对于一些具体的问题，某些部分彼此之间可能并无明显界限，可能相互渗透，可能合为一部分。但递归调用部分明显地区别于其他部分。1
2
3
4
5
6return_type divideAndConquer(objArray *p,int i , int j){
int tempInt;
if(simple(p,i,j)) return solve(p,i,j);
temp = divide(p,i,j);
return (combine(divideAndConquer(p,i,temp-1),divideAndConquer(p,temp,j)));
}
算法框架中要处理的对象以某数组（objArray）的形式存放，函数divideAndConquer()有三个输入参数：p,i,j。p是指向对象的指针，i、j是对象数组的两个下标，表明了函数处理对象的范围，函数divideAndConquer()首先调用了抽象函数simple(p,i,j)，它的功能是检查由i、j确定的问题规模足够小，如果足够小，则可以直接调用solve(p,i,j)函数得到简单情况的解；否则调用函数divide(p,i,j)，将问题规模划小，得到划分的中间下标用tempInt暂时保存，然后对两个子问题分别递归调用divideAndConquer(p,i,temp-1)和divideAndConquer(p,temp,j)，最后调用combine函数将两个解合并，得到原问题的解。假设op是实际处理对象的指针，对象数组的元素个数为n，在调用程序中执行函数调用divideAndConquer(op,0,n-1)可得到所求的解。
分治法应用
快速排序:-
每趟把一个元素放入排完序后它所应在的位置，这个位置把原数组分成两个宏观有序的子数组。
思想:
在待排序的n个元素中任取一个元素（通常取第一个元素）为分区标准，把所有小于该排序码的元素移到左边，把所有大于该排序码的元素移到右边，中间放所选的元素，这一整个过程称为一次排序；然后，对前后两个子序列分别重复上述过程，直到所有元素都排好序。
第一趟快速排序的具体流程：设置变量i指向参加排序的数组中第一个位置0，变量j指向参加排序的数组中最后一个位置n-1.首先保存元素array[0]，使得array[0]为空出的位置（空位在前一区），这时，令j向前扫描，寻找小于array[0]的元素，假设找到的元素是array[j]，将元素array[j]移到当前空位中；这时array[j]成为空位（空位在后一区），再令i自i+1起向后扫描，寻找大于array[0]排序码的元素，假设找到的元素是array[i]，将array[i]移到当前空位中，空位又到了前一区，然后再令j自j-1起向前扫描。如此交替改变扫描方向，从两端向中间靠拢，直到i=j，这是i（j）所指的位置为array[0]的最终位置。快速排序的记录移动次数不大于比较次数，所以，快速排序的最坏时间复杂度为O(n^2)，最好时间复杂度为O(nlog2n)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17void quickSort(int* array,int l,int r){
int i,j,t,temp;
if(l>r) return ; // 只有一个记录或者无记录，则无须排序
i=l;j=r;temp=array[i]; // temp中保存的即为基准数
while(i!=j){//寻找array[l]的最终位置
while(array[j]>=temp && i<j) --j;// 先从右往左扫描，查找第一个排序码小于temp的数
while(array[i]<=temp && i<j) ++i; // 再从左往右扫描，查找第一个排序码大于temp的数
// 交换两个两个数在数组中的位置
if(i<j){ t = array[i]; array[i] = array[j]; array[j] = t; } } // 最终将基准数归位，找到array[l]的位置
array[left] = array[i];
array[i] = temp;
quickSort(array,l,i-1);//递归处理左区间
quickSort(array,i+1,r); //递归处理右区间
return;
}
为改善最坏情况下的时间性能，可以采用三者取中规则，即在每一趟划分前，首先比较array[l]、array[r]和array[(l+r)/2]的大小，取中间的元素和array[l]交换。快速排序平均时间复杂度T(n)=O(nlog2n)，需要一个栈空间实现递归，栈大小取决与递归调用的深度，最多不超过n，若每次都选较大的部分进栈，处理较短的部分，则递归深度最多不超过log2n。快排不稳定，左右交换过程中无法保证原来相同排序码元素的相对位置不变。
归并排序:-
把规模为n的问题分成规模为[n/2]的两个子问题。
主要思想：
把待排序的数组分成若干子数组，先将每个子数组内的元素排序，再将已排序的子数组合并，得到完全排序的数组。合并时开始只要比较各子数组第一个元素的排序码，排序码最小的元素为排序后的第一个元素，取出该元素，继续比较各子数组的第一个元素，找出排序后的第二个元素，如此反复，经过一次扫描，得到排序结果。
两组归并算法:设array[low]到array[m]和array[m+1]到array[high]是存在同一个数组中且相邻的两个有序的子数组，两组归并算法将它们合并为一个有序的数组，并存在array1[low]到array1[high]中。
1 | void merge(int* array,int* array1,int low,int m,int high){ |
一趟归并的算法：设各子数组长度为length（最后一个子数组长度可能小于length），则array[0]到array[n-1]中共有n/length（向上取整）个有序的子数组，它们分别为：从array[0]到array[length-1]，从array[length]到array[2length-1],…,最后一个是从array[(n/length(向上取整)-1)length]到array[n-1]。在一趟归并中反复调用上面定义的merge操作，将相邻的一对对子数组归并。
1 | // 对array做一趟归并，结果放在array1中 |
二路归并算法：多次调用一趟归并过程，每趟归并欧有序子文件的长度length扩大一倍。
1 | void mergeSort(int* array,int n){ |
第i趟归并后，有序子数组长度为2^i，所以具有n个记录的数组排序，必须做log2n（向上取整）趟归并，每趟归并所花费的时间是O(n),二路归并排序算法的时间复杂度为O(nlog2n)。算法中增加了一个数组record，算法的辅助空间为O(n)，二路归并排序是稳定的。
