## 手写快排:
```cpp
#include<cstdio>
using namespace std;
int a[1000005];
inline void Quicksort(int *a,int l,int r){
int mid;
int tl=l,tr=r;//t是transform的缩写,表示转换
mid=a[(l+r)>>1];//分治
do{
while(a[tl]<mid){//在左半部分寻找比中间大的数
tl++;
}
while(a[tr]>mid){//在右半部分寻找比中间小的数
tr--;
}
if(tl<=tr){
int t=a[tl];
a[tl]=a[tr];
a[tr]=t;
tl++;
tr--;
}
}while(tl<=tr);
if(l<tr){
Quicksort(a,l,tr);
}
if(tl<r){
Quicksort(a,tl,r);
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
Quicksort(a,1,n);
for(int i=1;i<=n;i++){
printf("%d ",a[i]);
}
return 0;
}
```
比STL快。
by Delta_Cosh @ 2018-05-10 20:26:59
sort比手写快排快吧
by dingxingdi @ 2018-05-10 21:00:02
归并+氧气也可以:
```
#include <iostream>
using namespace std;
int a[1000001],bag[1000001],ans;
inline void gbsort(int l,int r) {
int mid=(l+r)/2,i=l,j=mid+1,k=l;
if (l==r)
return;
gbsort(l,mid);
gbsort(mid+1,r);
while (i<=mid&&j<=r) {
if (a[i]<=a[j]) {
bag[k]=a[i];
k++;
i++;
} else {
bag[k]=a[j];
k++;
j++;
ans+=mid-i+1;
}
}
while (i<=mid) {
bag[k]=a[i];
k++;
i++;
}
while (j<=r) {
bag[k]=a[j];
k++;
j++;
}
for (int h=l; h<=r; h++)
a[h]=bag[h];
}
int main() {
int n;
cin>>n;
for (register int i=1; i<=n; i++) {
cin>>a[i];
}
gbsort(1,n);
for (register int i=1; i<n; i++) {
cout<<a[i]<<' ';
}
return 0;
}
```
by Ice_watermelon @ 2018-05-10 21:01:23
sort可是少数的比手打快的STL啊
by Iowa_BattleShip @ 2018-05-10 21:16:16
@[Delta_Cosh](/space/show?uid=62575)
你手写的还真没有STL快
by Flaranis @ 2018-05-11 08:16:37
@[流风之回雪](/space/show?uid=58448) 哦,这样啊,我知道了。
by Delta_Cosh @ 2018-05-11 18:59:47
@[Delta_Cosh](/space/show?uid=62575) 谢谢大佬指教
by 37qwq @ 2018-05-12 11:24:24