AcWing 785. 快速排序
原题链接
简单
作者:
Emzie
,
2020-09-24 15:13:23
,
所有人可见
,
阅读 413
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
String[] s = br.readLine().split(" ");
int n = Integer.valueOf(str);
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.valueOf(s[i]);
}
quickSort(arr,0,n-1);
for (int i = 0; i < n; i++) {
System.out.print(arr[i]+" ");
}
}
public static void quickSort(int[] arr,int l,int r){
if(l>=r) return;
int x = arr[l];
int i = l-1;
int j = r+1;
while(i<j){
do i++; while(arr[i]<x);
do j--; while(arr[j]>x);
if(i<j) swap(arr,i,j);
}
quickSort(arr,l,j);
quickSort(arr,j+1,r);
}
public static void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}