AcWing 785. 快速排序
原题链接
简单
作者:
理想二旬.
,
2021-05-06 22:41:15
,
所有人可见
,
阅读 317
C++ 代码
import java.util.Scanner;
import java.io.BufferedInputStream;
class Main{
private static int N = 100010;
private static int[] a = new int[N];
public static void main(String[] args){
Scanner in = new Scanner(new BufferedInputStream(System.in));
int n = in.nextInt();
//读数据
for(int i = 0; i < n; i++){
a[i] = in.nextInt();
}
quickSort(a, 0, n - 1);
for(int i = 0; i < n; i++){
System.out.print(a[i] + " ");
}
}
public static void quickSort(int[] arr, int l, int r){
if(l >= r)
return;
//1. 确定边界点
int target = arr[l + r >> 1];
int left = l - 1;
int right = r + 1;
//2. 分区间
while(left < right){
do ++left; while(arr[left] < target);
do --right; while(arr[right] > target);
if(left < right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
//3. 递归
quickSort(arr, l, right);
quickSort(arr, right + 1, r);
}
}