AcWing 785. 快速排序
原题链接
简单
作者:
doubleSix
,
2021-01-11 19:17:34
,
所有人可见
,
阅读 280
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
using namespace std;
const int MAX = 1e9+7;
int num[100005];
void quick_sort(int L,int R)
{
if(L < R){
int t = num[(L+R)/2];
int l = L-1, r = R+1;
while(l < r){
do l++; while (num[l] < t);
do r--; while (num[r] > t);
if(l < r) swap(num[l],num[r]);
}
// 将第二次递归改为循环,可使递归栈严格小于log(n)
quick_sort(L,r);
quick_sort(r+1,R);
}
}
int main()
{
int N;
scanf("%d",&N);
for(int i = 0;i < N;i++){
scanf("%d",&num[i]);
}
quick_sort(0,N-1);
for(int i = 0;i < N;i++){
printf("%d ",num[i]);
}
return 0;
}