AcWing 785. 快速排序
原题链接
简单
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(infile.readLine());
int N = Integer.parseInt(st.nextToken());
int[] arr = readArr(N, infile, st);
quick_sort(arr, 0, arr.length - 1);
print(arr);
}
private static void quick_sort(int[] q, int l, int r) {
if (l >= r) return;
int x = q[l + (r - l) / 2], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j) {
int t = q[i];
q[i] = q[j];
q[j] = t;
}
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
public static int[] readArr(int N, BufferedReader infile, StringTokenizer st) throws Exception {
int[] arr = new int[N];
st = new StringTokenizer(infile.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
return arr;
}
public static void print(int[] arr) {
for (int x : arr) System.out.print(x + " ");
System.out.println();
}
}