AcWing 785. 快速排序
原题链接
简单
作者:
硬拉tom
,
2020-09-16 00:59:56
,
所有人可见
,
阅读 432
java 代码
import java.util.*;
public class Main{
static int N=100010;
static int[] a=new int[N];
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
qsort(a,0,n-1);
for(int i=0;i<n;i++){
System.out.print(a[i]+" ");
}
}
static void qsort(int[] a,int s,int e){
if(s>=e){
return;
}
int b=a[s+(e-s)/2],i=s-1,j=e+1,t;//下面i是先自增再判断,j先自减再判断,所以i=s-1,j=e+1
while(i<j){
do i++;
while(a[i] < b);
do j--;
while(a[j] > b);
if(i<j){
t=a[j];
a[j]=a[i];
a[i]=t;
}
}
qsort(a,s,j);//此时i>j,所以此处j不能换成i
qsort(a,j+1,e);
}
}