AcWing 785. 快速排序 (Java)
原题链接
简单
作者:
Georgehu
,
2020-03-26 22:56:02
,
所有人可见
,
阅读 3772
import java.util.Scanner;
import java.io.BufferedInputStream;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
private static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int x = arr[(left + right) / 2], i = left - 1, j = right + 1;
while (i < j) {
do {
i++;
} while (arr[i] < x);
do {
j--;
} while (arr[j] > x);
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
quickSort(arr, left, j);
quickSort(arr, j + 1, right);
}
}
我发现,当x取第一个数的时候会超时,应该是陷入死循环了,这个和老师说的不是很符合啊
最后一步的for循环这样写好一些for (int i = 0; i < n; i++) {
if(i != n - 1)
System.out.print(arr[i] + ” “);
else
System.out.print(arr[i]);
}
同问,这样就会使得速度变快了吗
大佬这个BufferedInputStream加在这里有什么用啊
加快java的输入
实际发现比Scanner还慢hhhhh
是的 用这个好慢!