分治算法实现归并排序
今天我们来学习归并排序，归并排序中也用到分治思想：就是把一个大的问题分解成多个小的问题，小的的问题能够直接或者容易得到解，然后再把小问题的解合并成大问题的解。其中离不开递归算法。
在学习归并排序之前，同学们先来思考一下这样一个问题：有两个有序的数组a和b，现在要求把这两个有序的数组合并成一个有序的数组c。如下图所示：
同学们可以看到，a数组和b数组中的元素都是有序的，现在要把它们合并成一个有序数组c，我们该如何操作呢？
我们首先给a数组，b数组，c数组各定义一个下标变量，分别是i，j，k他们的最开始都指向数组的第一个元素的位置。如下图所示：
我们下一步要做的是，比较当前a数组的元素和b数组的元素大小，把其中小的元素先存入到c数组中去。
因为要把所有的数都合并到c数组中去，对于a数组和b数组中的元素就要遍历，遍历用循环，循环的条件是i和j都要小于5。程序段如下：
同学们仔细分析该程序段。当a[i]<b[j]的时候，就把a[i]的元素写入到c[k]中去，同时k和i都自增1，即往后移动一个位置，准备比较和复制下一个数据。这时候b数组的指针位置不变。反之，b数组的元素复制到c数组中，且下标位置后移一个。然后继续比较。直到i<5且j<5条件不成立。就退出循环。
上述说的条件不成立，也就是说，a数组和b数组有一个数组是先结束的，先结束的它的所有元素应该都复制到c数组中去了，那么另一个数组肯定还有元素没有写入到c数组中去，下一步要继续判断i和j哪一个没有到达5，没有到达5的，就要把它后面的数继续写入c数组中去，我们用如下代码实现：
如该例，a数组i先到达5，而b数组中还有一个元素10没有写入c数组中去，这时候就会执行上述两个while语句中的第二个，因为第一个条件不成立。
这就是两个有序数组合并成一个有序数组的算法。同学们认真思考，动手书写程序，务必理解。
同学们记住这样的一句话：只有一个元素的数组，它就是一个有序的数组。
下面，我们就来讲解归并排序。
归并排序的思想是这样的：我们把一个无序的数组不断地折半分解，直到分解成一个元素的数组（它是有序的），然后再把这一个个有序的数组合并成一个数组，即实现了排序。
现在，我们要思考的是怎样分，分到什么时候结束，结束后，再合并。
步骤如下：
每次一半一半分，如果数组的长度不为1，则继续分（递），否则就进行合并（归）。
如上图，当分到图中间的时候，数组长度为1，这时候往下开始合并，最终合并成一个有序数组。
程序如下：
程序代码
#include<bits/stdc++.h>
using namespace std;
int arry[1000],arryT[1000];
void merge(int l,int mid,int r){
int i=l;
int j=mid+1;
int k=l;
while(i<=mid&&j<=r){
if(arry[i]<arry[j]){
arryT[k++]=arry[i++];
}else{
arryT[k++]=arry[j++];
}
}
while(i<=mid){
arryT[k++]=arry[i++];
}
while(j<=r){
arryT[k++]=arry[j++];
}
for(int i=l;i<=r;i++){
arry[i]=arryT[i];
}
}
void mergeSort(int l,int r){
int mid;
if(l<r){
mid=(l+r)/2;
mergeSort(l,mid);
mergeSort(mid+1,r);
merge(l,mid,r);
}
}
int main(){
int n;
cout<<"请输入数组的长度："<<endl;
cin>>n;
for(int i=0;i<n;i++){
cin>>arry[i];
}
//归并排序
mergeSort(0,n-1);
for(int i=0;i<n;i++){
cout<<arry[i]<<setw(5);
}
return 0;
}
长按二维码添加关注