二分归并排序
1. 问题
归并排序是建立在归并操作上的一种有效的排序算法,该算法是分治法的一个应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
2. 解析
二分归并排序的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
第四步：将排好序的数组的元素复制到原数组中。
例如：设有数列{4，3，2，1}
第一次归并后{3，4}，{1，2}
第二次归并后{1，2，3，4}
二分归并排序完成。
3. 设计
1 #include<stdio.h> 2 const int maxn=1000+10; 3 int n; 4 int a[maxn]; 5 int tmp[maxn]; 6 /*----------以下为二分归并排序算法----------*/ 7 void Merge_Sort(int a[],int l,int r){ 8 if(l>=r)return; 9 int mid=(l+r)/2; 10 Merge_Sort(a,l,mid); 11 Merge_Sort(a,mid+1,r); 12 int now=l-1; 13 int i=l,j=mid+1; 14 while(i<=mid&&j<=r){ //两部分合并 15 if(a[i]<a[j]){ 16 tmp[++now]=a[i]; 17 ++i; 18 } 19 else{ 20 tmp[++now]=a[j]; 21 ++j; 22 } 23 } 24 while(i<=mid){ 25 tmp[++now]=a[i]; 26 ++i; 27 } 28 while(j<=r){ 29 tmp[++now]=a[j]; 30 ++j; 31 } 32 for(int i=l;i<=r;++i){ 33 a[i]=tmp[i]; 34 } 35 } 36 /*----------以上为二分归并排序算法----------*/ 37 int main(){ 38 scanf("%d",&n); 39 for(int i=1;i<=n;++i)scanf("%d",&a[i]); 40 Merge_Sort(a,1,n); 41 for(int i=1;i<=n;++i){ 42 printf("%d%c",a[i],i==n?' ':' '); 43 } 44 }
4. 分析
算法复杂度：O(nlogn)
分析：递归分解数据，需要递归logN次，每次都需要对n个数据扫描一次，最好最坏平均都一样，所以O(nlogn)。
1.首先可知
f（n）=2f（n/2）+n
f（n）表示对n个数进行归并排序
2f（n/2）表示将n个数分成两部分分别进行归并排序
n表示对两个子过程结束之后合并的过程。
2.推导
f(n/2)=2*f(n/4)+n/2 当n=n/2时
f(n/4)=2*f(n/8)+n/4 当n=n/4时
……
f(n/2^(m-1))=2*f(n/(2^m))+n/2^(m-1) 当n=n/2^(m-1)时
3.由此可得
f(n)=2^m*f(n/(2^m))+m*n
当m足够大时（仅剩一个数字时），可使得 n/（2^m）=1,此时m=log2（n）
将m代入原式得f(n)=2^(log2(n))*f(1)+n*log2(n),即f(n)=nlog(n)
5. 源码
https://github.com/JayShao-Xie/algorithm-work/blob/master/Merge_Sort.cpp