一、基础知识
1. 分治法的思想：
将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
2. 满足分治策略的条件：
1) 该问题缩小到一定规模就可以解决；
2) 该问题可以分解为若干个规模较小的相同的问题，即该问题具有最优子结构；
3) 利用该问题分解出的子问题可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
3. 分治模式在每层递归时的三个步骤：
1) 分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。
2) 解决这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解。
3) 合并这些子问题的解成原问题的解。
二、应用
1.归并排序
归并排序思想：
1） 分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。2） 解决：使用归并排序递归地排序两个子序列，直到子序列规模为1为止。
3） 合并：合并两个已排序的子序列以产生已排序的答案。
归并过程为：比较A[i]和B[j]的大小，若A[i]≤B[j]，则将第一个有序表中的元素A[i]复制到C[k]中，并令i和k分别加上1；否则将第二个有序表中的元素B[j]复制到C[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到C中从下标k到下标t的单元。
void mergeArray(int A[], int a,int B[],int b,int C[])
{
int i,j,k;
i=j=k=0;
while(i<a&&j<b)
{
if(A[i]<B[j])
C[k++]=A[i++];
else
C[k++]=B[i++];
}
while (i<a)
{
C[k++]=A[i++];
}
while(j<b)
{
C[k++]=B[i++];
}
}
void mergeArray(int A[],int first,int mid,int last,int temp[]){int i=first,j=mid,m=mid+1,n=last,k=0;while(i<=j&&m<=n){if(A[i]<A[m])temp[k++]=A[i++];elsetemp[k++]=A[m++];}while(i<=j)temp[k++]=A[i++];while(m<=n)temp[k++]=A[m++];for(i=0;i<k;i++){A[first+i]=temp[i];}}
归并排序的算法我们通常用递归实现，先把待排序区间[first,last]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[first,last]。代码如下：
void mergeSort(int A[],int first,int last,int C[])
{
if(first<last)
{
int mid=(first+last)/2;
mergeSort(A,first,mid,C);
mergeSort(A,mid+1,last,C);
mergeArray(A,first,mid,last,C);
}
}
bool mergeSort(int A[],int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergeSort(A, 0, n - 1, p);
delete[] p;
for(int i=0;i<n;i++)
{
cout<<A[i]<<" ";
}
return true;
}
比如归并{1,-1,2,-3,4,-5,6,-7}，程序输出是这样的：
2. 快速排序
快速排序思想：
1) 分解：数组A[p...r]被划分为两个（可能为空）字数组A[p...q-1]和A[q+1...r]，使得A[p...q-1]中的每一个元素都小于等于A[q]，而A[q]也小于等于A[q+1...r]中的每个元素。其中，计算下标q也是划分过程的一部分。
2) 解决：通过递归调用快速排序，对子数组A[p...q-1]和A[q+1...r]进行排序。
3) 合并：因为子数组都是原址排序的，所以不需要合并操作：数组A[p...r]已经有序。
代码：
int Partition(int array[],int low,int high)
{
int temp=array[low]; //保存下子表的第一个记录
int pivotkey=array[low]; //枢轴记录关键字
while(low<high) //从表的两端向中间开始扫面
{
while(low<high&&array[high]>=pivotkey)
--high;
array[low]=array[high]; //将比枢轴小的移动到低端
while(low<high&&array[low]<=pivotkey)
++low;
array[high]=array[low]; //将比枢轴大的移动到高端
}
array[low]=temp; //枢轴记录到位
return low; //返回枢轴位置
}
void QSort(int array[],int low,int high) { int piv; if(low<high) { piv=Partition(array,low,high); QSort(array,low,piv-1); QSort(array,piv+1,high); } }
3、最大子数组
问题：在一个数组中寻找子数组，要求子数组的元素连续且元素的总和能够达到最大。
利用分治法的思想：
1)分解：分解n个元素的数组为序列成各具n/2个元素的两个子序列：A[low,mid]和A[mid+1,high]。此时最大子数组可能位于下面三种情况之一：1）完全位于左子数组A[low,mid]中，low<=i<=j<=mid。2）完全位于子数组A[mid+1,high]中，mid<=i<=j<=high。3）跨越了重点，因此low<=i<=mid<j<=high。2)解决：递归的求解分解的两个子序列。
3)合并：比较三种情况的解，并保留最大者。
在上述分治法中，每次迭代都分解出3个子问题，其中两个子问题需要递归解决，第3个子问题则可直接求解出来。
代码：
int FindMaxCrossSubarray(int A[], int low, int mid, int high) //跨越
{
int left_sum = Infinite;
int sum = 0;
for (int i = mid; i >= low; i--) //左半部的最大子数组
{
sum += A[i];
if (sum >left_sum)
{
left_sum = sum;
max_left = i;
}
}
int right_sum = Infinite;
sum = 0;
for (int i = mid + 1; i <= high; i++) //右半部的最大子数组
{
sum += A[i];
if (sum > right_sum)
{
right_sum = sum;
max_right = i;
}
}
return left_sum + right_sum;
}
int FindMaxSubarray(int A[], int low, int high)
{
int left_sum, right_sum, cross_sum;
if (high == low) //一个元素
{
return A[low];
}
else
{
int mid = (low + high) / 2; //分治
left_sum = FindMaxSubarray(A, low, mid); //前半部
right_sum = FindMaxSubarray(A, mid + 1, high); //后半部
cross_sum = FindMaxCrossSubarray(A, low, mid, high); //跨越前后
if (left_sum >= right_sum && left_sum >= cross_sum) //最大子数组在左边
return left_sum;
else if (right_sum >= left_sum && right_sum >= cross_sum) //右边
return right_sum;
else //跨越
return cross_sum;
}
}
4.寻找逆序数对
问题：有N个整数，A[1],A[2],...,A[n]。需要找到这样的(i,j)的数对的数量，满足：1<=i<j<=N,A>A[j]。数据范围：1<=N<=65537,0<=A<=10e9
利用分治法的思想：
利用归并排序，在归并排序的过程中对逆序对进行统计。回想排成升序的递归排序，假设现在要合并A和B两个子区间。根据归并排序算法，A和B是相邻的。假设A在B的左边，现在正在比较A和B[j]而且A>B[j]，那么A，A[i+1]，...，A[A.length]都与B[j]构成逆序对，因为在归并过程中对于每一个B[j]都会找到第一个大于它的A，所以只需要顺便统计下即可求出答案。代码：
onst int LENGTH=100;
int temp[LENGTH]; //额外的辅助数组
int count=0;
void Merge(int * array,int first,int med,int last)
{
int i=first,j=med+1;
int cur=0;
while (i<=med&&j<=last)
{
if (array[i]<array[j])
{
temp[cur++]=array[i++];
}
else
{
temp[cur++]=array[j++];
<span style="color:#ff0000;">count+=med-i+1</span>; //核心代码，逆序数增加
}
}
while (i<=med)
{
temp[cur++]=array[i++];
}
while (j<=last)
{
temp[cur++]=array[j++];
}
for (int m=0;m<cur;m++)
{
array[first++]=temp[m++];
}
}
void MergeSort(int *array,int first,int last)
{
if (first==last)
{
return ;
}
int med=first+(last-first)/2;
MergeSort(array,first,med);
MergeSort(array,med+1,last);
Merge(array,first,med,last);
}