归并排序
学了一下归并排序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<iostream> #include<cstdio> using namespace std; int num[100001],n; void merge(int *num,int *a,int l,int r) { int i=l,j,k=l,m=(l+r)>>1; for(j=m+1;i<=m&&j<=r;k++) { if(num[i]<=num[j])a[k]=num[i++]; else a[k]=num[j++]; } while(i<=m)a[k++]=num[i++]; while(j<=r)a[k++]=num[j++]; } void sort(int *num,int *a,int l,int r) { if(l==r)a[l]=num[l]; else { int t[100001]; int m=(l+r)>>1; sort(num,t,l,m); sort(num,t,m+1,r); merge(t,a,l,r); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&num[i]); sort(num,num,1,n); for(int i=1;i<=n;i++)printf("%d ",num[i]); return 0; } |
Subscribe