《算法分析》作业4 1. 问题 2. 解析 3. 设计 4. 分析 5. 源码
对n个不同的数构成的数组A[1..n]进行排序，其中n=2^k，要求用归并排序进行排序。
2. 解析
归并排序：当我们要对数组进行排序的时候，我们首先把这个数组分成一半，然后就是对左边的数组和右边的数组分别进行排序，之后将他们合并起来，然而对左右两边数组进行排序的时候要用到分治的思想，对左右两个数组进行归并排序，也就是说还得将左右两个数组在分成一半，然后对每个部分进行排序，再归并。
如图模拟了归并的过程：
3. 设计
void merge(int l,int r,int mid)//排序过程 { int aux[r-l+1],i,j; rep(k,l,r) aux[k-l]=a[k]; i=l; j=mid+1; rep(k,l,r) { if(i>mid) { a[k]=aux[j-l]; j++; } else if(j>r){ a[k]=aux[i-l]; i++; } else if(aux[i-l]>aux[j-l]) { a[k]=aux[j-l]; j++; } else { a[k]=aux[i-l]; i++; } } } void merge_sort(int l,int r)//归并 { if(l>=r)return ; int mid=(l+r)>>1; merge_sort(l,mid); merge_sort(mid+1,r); merge(l,r,mid); }
4. 分析
复杂度分析：每次二分进行O(n)遍历，二分的复杂度为log(n)所以总的复杂度就是T=O(nlogn)
5. 源码
https://github.com/xiaojunjun601/sfHomework1/blob/master/%E4%BB%A3%E7%A0%81/guibing.cpp