归并排序模板

分治思想

  1. 确定分界点：$mid = (l+r)/2$

  2. 先递归分成左右两边

  3. 将两个有序数组合并成一个有序序列——归并

    使用两个指针：这个过程时间复杂度为$O(n)$

整体时间复杂度$O(nlogn)$

因为分层用了$logn$次

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
49
50
51
52
53
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        merge_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 merge_sort(int[] q, int l, int r) {
        if (l >= r) return;
        // 确定分界点
        int mid = l + ((r - l) >> 1);
        // 递归
        merge_sort(q, l, mid);
        merge_sort(q, mid + 1, r);

        int[] tmp = new int[r - l + 1]; // 辅助数组
        // 归并
        int k = 0; // 表示tmp中有多少个数
        // 两个指针
        int i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (q[i] <= q[j]) {
                tmp[k++] = q[i++];
            } else {
                tmp[k++] = q[j++];
            }
        }
        // 剩余
        while (i <= mid) tmp[k++] = q[i++];
        while (j <= r) tmp[k++] = q[j++];
        // 放回
        for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    }
}