基本原理

归并排序运用了分治的思想,先将数组二分成一个元素(一个元素时看为有序),然后将这些元素不断合并,每合并一次排一次序,最后就可以得到有序的数组。

比如说一个序列:12 ,23,1,44,233,10,9,8。我们先分成两段:12 ,23,1,44 和 233,10,9,8,
发现还能再分成4段:12 ,23 和 1,44———233,10 和 9,8。
再分成8段:12—23—1—44 和233—10—9—8。
这时候开始把子序列进行排序合并,一个元素就是有序的。所以不用排序。
合并成2个一组排序得到:12,23——1,44—-10,233—-8,9。
再合并成4个一组排序得到:1,12,23,44—-8,9,10,233。
最后合并得到最终结果:1,8,9,10,12,23,44,233。

合并过程看代码

链接:https://www.jianshu.com/p/b50a6034eb90

图解

这个图片蓝色部分就是拆的过程,而绿的部分为并的过程

代码实现

void paixu(int first,int mid,int last,int a[],int temp[])//这是合并过程
{
int l1=first,l2=mid+1,r1=mid,r2=last;
int k=0;
while(l1<=r1&&l2<=r2)//两部分都存在时看哪个小就加上哪个
{
if(a[l1]<=a[l2])
{
temp[k++]=a[l1++];
}
else
{
temp[k++]=a[l2++];
}
}
while(l1<=r1)//第一部分有剩余就把第一部分剩下的全加上
{
temp[k++]=a[l1++];
}
while(l2<=r2)
{
temp[k++]=a[l2++];
}
for(int i=0;i<k;i++)
{
a[i+first]=temp[i];
}
}
void xunhuan(int first,int last,int a[],int temp[])
{
if(first<last)
{
int mid=(first+last)/2;
xunhuan(first,mid,a,temp);//拆左边
xunhuan(mid+1,last,a,temp);//拆右边
paixu(first,mid,last,a,temp);//合并
}
}
bool mergesort(int a[],int first,int last)
{
int* p=new int[last-first];//建一个临时数组,合并时用
if(p==NULL)//判断是否传入空数组
{
return false;
}
xunhuan(first,last,a,p);
delete [] p;
return true;
}