vlambda博客
学习文章列表

今天我们来学习归并排序，归并排序中也用到分治思想：就是把一个大的问题分解成多个小的问题，小的的问题能够直接或者容易得到解，然后再把小问题的解合并成大问题的解。其中离不开递归算法。

在学习归并排序之前，同学们先来思考一下这样一个问题：有两个有序的数组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;

}