快速排序模板

  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);
    }


}