C++归并排序算法实例
归并排序
归并排序算法是采用分治法的一个非常典型的应用。归并排序的思想是将一个数组中的数都分成单个的；对于单独的一个数，它肯定是有序的，然后，我们将这些有序的单个数在合并起来，组成一个有序的数列。这就是归并排序的思想。它的时间复杂度为O(N*logN)。
代码实现
#include<iostream>
usingnamespacestd;
//将有二个有序数列a[first...mid]和a[mid...last]合并。
voidmergearray(inta[],intfirst,intmid,intlast,inttemp[])
{
inti=first,j=mid+1;
intm=mid, n=last;
intk=0;
while(i<=m&&j<=n)
{
if(a[i]<=a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=m)
temp[k++]=a[i++];
while(j<=n)
temp[k++]=a[j++];
for(i=0;i<k;i++)
a[first+i]=temp[i];
}
voidmergesort(inta[],intfirst,intlast,inttemp[])
{
if(first<last)
{
intmid=(first+last)/2;
mergesort(a,first,mid,temp); //左边有序
mergesort(a,mid+1,last,temp);//右边有序
mergearray(a,first,mid,last,temp);//再将二个有序数列合并
}
}
boolMergeSort(inta[],intn)
{
int*p=newint[n];
if(p==NULL)
returnfalse;
mergesort(a,0,n-1,p);
delete[]p;
returntrue;
}
intmain()
{
intarr[]={2,1,4};
MergeSort(arr,3);
for(inti=0;i<3;++i)
{
cout<<arr[i]<<"";
}
cout<<endl;
}