众所周知,vector 插入时间复杂度其实约等于 $O(\log n)$
by WsW_ @ 2024-01-31 10:13:50
sort不香吗
by big_clever222 @ 2024-01-31 10:34:33
cstdio流的我刚刚归并起手(因为不想写`using namespace std;`)
$Code$
```
#include<cstdio>
const int N=1e5+5;
int n,a[N],b[N];
void sort(int l,int r){
if(l==r)
return;
sort(l,l+r>>1);
sort((l+r>>1)+1,r);
int len=l,len2=(l+r>>1)+1,len3=l;
while(len<=(l+r>>1)&&len2<=r){
if(a[len]<a[len2])
b[len3++]=a[len++];
else
b[len3++]=a[len2++];
}
while(len<=(l+r>>1))
b[len3++]=a[len++];
while(len2<=r)
b[len3++]=a[len2++];
for(int i=l;i<=r;i++)
a[i]=b[i];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
sort(1,n);
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
putchar('\n');
return 0;
}
```
by M_K_W_ @ 2024-01-31 12:02:27