快速排序模板

  1. 先确定分界点:$q[l] 、 q[(l+r)/2]、 q[r]$ 或随机
  2. 调整区间:小于等于x的在左半边,大于等于x的在右半边 (如何去调整)
  3. 递归处理左右两段

由数据反推算法复杂度和算法内容

实现

暴力:

  • 声明两个数组 a[] 、b[]
  • 将$q[l~r]$ 遍历
  • 如果 $q[i] \le x$ 放到a[]中
  • 如果 $q[i] \ge x$ 放到b[]中
  • 再将a、b数组放回q中

优美:

用两个指针,swap

关于JAVA中IO流类:BufferredReader的简单用法

bufferreader要比scanner快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package code;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;

public class 快排模板 {

public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(input.readLine());
int[] q = new int[n];
String[] linelist = input.readLine().split(" ");
for (int i = 0; i < linelist.length; i++) {
q[i] = Integer.parseInt(linelist[i]);
}

quick_sort(q, 0, q.length - 1);

for (int i = 0; i < q.length; i++) {
System.out.print(q[i]);
System.out.print(" ");
}

}

public static void quick_sort(int[] q, int l, int r) {
if (l >= r) return;
int x = q[l];
int i = l - 1;
int j = r + 1;
while (i < j) {
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j) {
int t = q[i];
q[i] = q[j];
q[j] = t;
}
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}


}