AcWing 785. Java快速排序(详细注解)
原题链接
简单
作者:
JRnonr
,
2022-04-01 21:25:08
,
所有人可见
,
阅读 109
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));//BufferedReader比Scanner快
int n = Integer.parseInt(br.readLine());
int[] arr= new int[n];
String[] res = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(res[i]);
}
quickSort(arr,0,n-1);
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
public static void quickSort(int[] q,int l,int r){//l指数组左端点的索引,r指数组右端点的索引
if(l>=r){
return;
}
int x=q[(l + r) / 2];
//定义i指针和j指针,因为后面的方法是先移动再判断,如果时i=l,j=r,则会从移动后的l+1和r-1进行遍历,导致两端点未参与比较
int i=l-1;
int j=r+1;
/*
通过左边的i指针遍历左边的数据,通过右边的j指针遍历右边的数据
当i指针对应的值>x时,暂停在当前位置,当j指针对应的值<x时,暂停在当前位置
如果都暂停后,i<j,需要将i处的值与j处的值交换,继续遍历
*/
while(i<j){
do{
i++;
}while(q[i]<x);
do{
j--;
}while(q[j]>x);
if(i<j){
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
//如果运行至i>=j,说明此时j右边的值都>=j+1左边的值
//需要通过递归quickSort再对两边各自进行排序
quickSort(q,l,j);
quickSort(q,j+1,r);
}
}