归并排序

戏志才 · 2019-06-18 13:18:35 · 个人记录

include<bits/stdc++.h>

using namespace std; void merge(int,int,int); void sorrt(int,int); int a[100050]={1},n,tp1[100050],tp2[100050];

void sorrt(int low,int up){

if(low>=up)return; 

int mid=(low+up)/2;

sorrt(low,mid);
sorrt(mid+1,up);

merge(low,mid,up);

}

void merge(int low,int mid,int up){

memset(tp1,0x7f,sizeof(tp1)); 
memset(tp2,0x7f,sizeof(tp2));  
for(int i=low;i<=mid;i++){
    tp1[i]=a[i];
}
for(int i=mid+1;i<=up;i++){
    tp2[i]=a[i];
}

int ii=low,jj=mid+1;
for(int k=low;k<=up;k++){
    if(tp1[ii]<=tp2[jj]){
        a[k]=tp1[ii];
        ii++; 
    }
    else{
        a[k]=tp2[jj];
        jj++; 
    } 
} 

}

int main(){ cin>>n;

for(int i=1;i<=n;i++){
    cin>>a[i];

}
sorrt(1,n); 

for(int i=1;i<=n;i++)cout<<a[i]<<" "; 
return 0;

}