AcWing 785. 快速排序
原题链接
简单
作者:
帅小柏
,
2021-01-14 11:39:07
,
所有人可见
,
阅读 3
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n;
int a[N];
void quick_sort(int a[],int l,int r)
{
if(l>=r) return ; // 边界
int i=l-1,j=r+1,x=a[l+r>>1]; // 因为要用 do..while 所以指向边界两端的前一个 即 i=l-1,j=r+1 .
// l+r>>1 等价于 (l+r)/2
while(i<j)
{
do i++; while(a[i]<x);
do j--; while(a[j]>x);
if(i<j) swap(a[i],a[j]);
}
quick_sort(a,l,j);
quick_sort(a,j+1,r);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
quick_sort(a,1,n);
for(int i=1;i<=n;i++) printf("%d ",a[i]);
return 0;
}