AcWing 785. 快速排序
原题链接
简单
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
String[] str = new String[n];
str = br.readLine().split(" ");
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(str[i]);
}
quick_sort(arr, 0, n-1);
for(int i=0; i<n; i++) {
System.out.print(arr[i] + " ");
}
}
private static void quick_sort(int[] arr, int l, int r) {
if(l >= r) return;
int i = l-1, j = r+1, x = arr[(l+r) >> 1];
while(i<j) {
do i++; while(arr[i] < x);
do j--; while(arr[j] > x);
if(i < j) {
int swap = arr[i];
arr[i] = arr[j];
arr[j] = swap;
}
}
quick_sort(arr, l, j);
quick_sort(arr, j+1, r);
}
}