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; }