代码板子如下:
#include<iostream> using namespace std; const int N = 1e6+10; int n; int q[N],tmp[N]; void merge_sprt(int q[N],int l,int r) { if(l>=r)return; int mid=(l+r)/2; merge(q,l,mid),merge(q,mid+1,r); //对整个数组进行区间划分,每次都是区间长度/2 //所以要划分logn次,区间长度为n,所以时间复杂度为(nlogn) int k=0,i=l,j=mid+1; while(i<mid&&j<=r) { if(q[i]<=q[j])tmp[k++]=q[i++]; else tmp[k++]=q[j++]; } while(i<=mid)tmp[k++]=q[i++]; while(j<=r)tmp[k++]=q[j++]; for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j]; } int main() { scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d",&q[i]); merge_sort(q,0,n-1); for(int i=0;i<n;i++)printf("%d ",q[i]); }
后续会再补上图帮助理解哒!!!