分治的基本概念

把一个任务，分成形式和原任务相同，但规模更小的几个部分任务(通常是两个部分)，分别完成，或只需要选一部完成。然后再处理完成后的这一个或几个部分的结果，实现整个任务的完成。

 分治的典型应用: 归并排序

数组排序任务可以如下完成:

1) 把前一半排序

2) 把后一半排序

3) 把两半归并到一个新的有序数组，然后再拷贝回原数组，排序完成。

 

#include 
     
      using namespace std;void Merge(int a[],int s,int mid,int e,int tmp[]){    int p1=s,p2=mid+1,p3=0;    while(p1<=mid && p2<=e)    {        if(a[p1]<=a[p2])            tmp[p3++]=a[p1++];        else            tmp[p3++]=a[p2++];    }    while(p1<=mid)        tmp[p3++]=a[p1++];    while(p2<=e)        tmp[p3++]=a[p2++];    int cnt=0;    for(int i=s; i<=e; i++)        a[i]=tmp[cnt++];}void MergeSort(int a[],int s,int e,int tmp[]){    if(s