AcWing 785. 快速排序
原题链接
简单
作者:
将情怀讲泛滥的恶果
,
2021-05-17 15:54:06
,
所有人可见
,
阅读 278
java
public class Main {
public static void main(String[] args) throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
int num = Integer.parseInt(br.readLine());
int[] arrs = new int[num];
String[] res = br.readLine().split(" ");
for (int i = 0; i < res.length; i++) {
arrs[i] = Integer.parseInt(res[i]);
}
quickSort(arrs, 0, arrs.length - 1);
for (int i = 0; i < arrs.length; i++) {
System.out.print(arrs[i] + " ");
}
br.close();
}
public static void quickSort(int[] nums, int left, int right) {
if (left >= right) return;
int p = left - 1;
int q = right + 1;
int key = nums[(left + right) >> 1];
while (p < q) {
while (true) {
p += 1;
if (nums[p] >= key) {
break;
}
}
while (true) {
q -= 1;
if (nums[q] <= key) {
break;
}
}
if (p < q) {
int temp = nums[p];
nums[p] = nums[q];
nums[q] = temp;
}
}
quickSort(nums, left, q);
quickSort(nums, q + 1, right);
}
}