归并排序——分治

一，首先先介绍分治的思想：

  把一个任务，分成形式和原任务相同，但规模更小的几个部分任务（通常是两个部分），分别完成，

或只需要选择一部完成，完成后的这一个或几个部分的结果，实现整个任务的完成。  

  下面来举个例子：16个硬币，有可能有一枚假币，假币比真币轻。有一天平，用最少称量次数确定有没有假币，若有的话，假币是那一枚（之前枚举例题的第二题有类似的问题可以复习一下）。

 二，分治排序：

就是前一半排序，后一半排序，然后再归并到一起。后面直接上代码剩下的解释放在代码中

首先看主函数：

int main(){
    int size = sizeof(a)/sizeof(int);
    MergeSort(a,0,size-1,b);
    for(int i = 0;ii){
        cout<",";
    }
    cout<<endl;
    return 0;
} 

这个主函数就没啥要解释的了

看分治函数：

void MergeSort(int a[],int s,int e,int tmp[]){
    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);
    }
}

这个函数就是使用前面所讲的递归的方法进行分治，参数的设计：首先是需要进行排序的数组a，然后是分治所要开始区间的起始区间s，结束区间e，和暂时储存的数组tmp。首先判断是不是只有一个数了，如果只有一个数的话，分治结束。之后有一个中间变量m进行分割（这个m其实就是递归进行的核心语句了）对左边进行分治，然后再对右边进行分治。分治全部完毕之后将这些分割出来的部分全部归并。

看归并函数：

void Merge(int a[],int s,int m,int e,int tmp[]){
    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;i1;i++){
        a[s+i] = tmp[i];
    }
}

现在来解释一下归并。将分治的两个部分相应下标比较大小，将小的部分放到tmp数组里面，然后把对应部分的下标加一，当有任何一半的到达终点就把循环暂停。随后再把剩下部分放到tmp中。但是这个算法一定要注意啊，进行这样归并的两个数组必须是排好序的否则可能导致后面的数组会无序。

这个就要涉及到前面的递归过程是怎么分割的了。

这个递归过程最好自己有笔过一遍对后面的数据结构的学习有好处。