785. 快速排序
Problem: 785. 快速排序
文章目录
- 思路
- 解题方法
- 复杂度
- Code
- 方法一（调用系统类库）
- 方法二（随机快速排序经典版）
- 方法三 （利用荷兰国旗问题改写快排）
思路
这个问题要求实现快速排序算法，对给定的整数数组进行从小到大的排序。 快速排序算法的工作原理是从数组中选择一个“枢轴”元素，然后将其他元素分区为两个子数组，一个包含小于枢轴的元素，另一个包含大于枢轴的元素。然后通过对两个子数组递归调用快速排序算法进行排序。
快速排序的时间复杂度在最好和平均情况下为O(n log n)，在最坏情况下为O(n^2)，但对于大多数输入，最坏情况并不常见。空间复杂度为O(log n)到O(n)，取决于快速排序的版本，并假设不计算存储输入所需的空间。
解题方法
- 方法一（调用系统类库）：这种方法是最简单的，直接调用Java的Arrays.sort()方法对数组进行排序。
- 方法二（随机快速排序经典版）：这种方法是快速排序的经典实现，通过随机选择一个元素作为枢轴，然后将数组分为两部分，一部分是小于枢轴的元素，另一部分是大于枢轴的元素，然后对这两部分分别进行快速排序。
- 方法三（利用荷兰国旗问题改写快排）：这种方法是快速排序的一个变种，通过将数组分为三部分，一部分是小于枢轴的元素，一部分是等于枢轴的元素，一部分是大于枢轴的元素，然后对小于枢轴和大于枢轴的两部分分别进行快速排序。
复杂度
时间复杂度:
时间复杂度在最好和平均情况下是 O ( n l o g n ) O(n log n) O(nlogn)，在最坏情况下是 O ( n 2 ) O(n^2) O(n2)。
空间复杂度:
空间复杂度是 O ( l o g n ) O(log n) O(logn)。
Code
方法一（调用系统类库）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static StreamTokenizer sr = new StreamTokenizer(in);
static int n;
static int MAXN = 100001;
static int[] arr = new int[MAXN];
public static void main(String[] args) throws IOException {
n = nextInt();
for(int i = 0; i < n; i++) {
arr[i] = nextInt();
}
Arrays.sort(arr, 0, n);
StringBuffer sb = new StringBuffer();
for(int i = 0; i < n; i++) {
sb.append(arr[i]);
sb.append(" ");
}
out.println(sb);
out.flush();
}
static int nextInt() throws IOException {
sr.nextToken();
return (int) sr.nval;
}
}
方法二（随机快速排序经典版）
未通过所有样例，这种方法不推荐
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static StreamTokenizer sr = new StreamTokenizer(in);
static int n;
static int MAXN = 100001;
static int[] arr = new int[MAXN];
public static void main(String[] args) throws IOException {
n = nextInt();
for (int i = 0; i < n; i++) {
arr[i] = nextInt();
}
quickSort(0, n - 1);
StringBuffer sb = new StringBuffer();
for (int i = 0; i < n; i++) {
sb.append(arr[i]);
sb.append(" ");
}
out.println(sb);
out.flush();
}
public static void quickSort(int l, int r) {
if (l >= r) {
return;
}
int x = arr[l + (int) (Math.random() * (r - l + 1))];
int mid = partition(l, r, x);
quickSort(l, mid - 1);
quickSort(mid + 1, r);
}
private static int partition(int l, int r, int x) {
int a = l, xi = 0; // 记录等于x的位置
for (int i = l; i <= r; i++) {
if (arr[i] <= x) {
swap(a, i);
if (arr[a] == x) {
xi = a;
}
a++;
}
}
swap(xi, a - 1);
return a - 1;
}
private static void swap(int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int nextInt() throws IOException {
sr.nextToken();
return (int) sr.nval;
}
}
方法三 （利用荷兰国旗问题改写快排）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static StreamTokenizer sr = new StreamTokenizer(in);
static int n;
static int MAXN = 100001;
static int[] arr = new int[MAXN];
public static void main(String[] args) throws IOException {
n = nextInt();
for (int i = 0; i < n; i++) {
arr[i] = nextInt();
}
quickSort(0, n - 1);
StringBuffer sb = new StringBuffer();
for (int i = 0; i < n; i++) {
sb.append(arr[i]);
sb.append(" ");
}
out.println(sb);
out.flush();
}
public static int first, last;
public static void quickSort(int l, int r) {
if(l >= r) {
return;
}
int x = arr[l + (int) (Math.random() * (r - l + 1))];
partition(l, r, x);
quickSort(l, first - 1);
quickSort(last + 1, r);
}
private static void partition(int l, int r, int x) {
if(l >= r) {
return;
}
first = l;
last = r;
int i = l;
while(i <= last) {
if(arr[i] == x) {
i++;
} else if(arr[i] < x) {
swap(i++, first++);
} else {
swap(i, last--);
}
}
}
private static void swap(int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int nextInt() throws IOException {
sr.nextToken();
return (int) sr.nval;
}
}