Home 归并排序
Post
Cancel

归并排序

Posted Aug 13, 2025
By GwanSY
8 min read

思路

  1. 总体框架
    • 左部分排好序、右部分排好序，利用 merge 过程让 整体 有序。
    • merge 的核心是：谁小拷贝谁，直到左右两部分数字耗尽，然后把辅助区间拷回原数组。
  2. 两种实现
    • 递归版：自顶向下分治。
    • 非递归版：自底向上，步长 step 从 1 开始每次乘 2，把相邻的两个有序块进行合并。
  3. 复杂度
    • 时间复杂度：T(n)=2T(n/2)+O(n) = O(n log n)
    • 额外空间：O(n)（需要辅助数组 help 来暂存合并结果）
    • 为什么比 O(n^2) 快？ 因为比较/移动是有组织的分治合并，几乎没有“无效比较/移动”。
  4. 关于“原地归并排序”
    • 有些资料说能做到 O(1) 额外空间，但通常会把时间复杂度拖到 O(n^2)，不推荐在工程/竞赛中使用。
  5. 归并分治的便利性
    • 归并的结构天然适合很多“统计/计数/对数”类问题（如逆序对、区间和、带限制的跨段统计等），能在 merge 时顺手做统计。

递归版

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
54
55
56
57
58
59
60
61
62
63
64
65

  /*
     1) 左部分排好序、右部分排好序，利用 merge 过程让整体有序
     2) merge：谁小拷贝谁，最后把辅助区间拷回原数组
     3) 递归实现 & 非递归实现（自底向上 step *= 2）
     4) 时间复杂度 O(n log n)
     5) 额外空间 O(n)（需要 help 数组）；“原地归并”虽省空间但常导致 O(n^2)，不推荐
     6) 归并分治是很多题的利器（逆序对、区间统计等）
    */
   
    public static int MAXN = 5000001;
    public static int[] arr = new int[MAXN];
    public static int[] help = new int[MAXN];
    public static int n;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF){
            n = (int) in.nval;
            for(int i = 0;i<n;i++){
                in.nextToken();
                arr[i] = (int) in.nval;
            }
            mergeSort1(0,n-1); //递归方法
            mergeSort2(); //非递归方法
            out.print(arr[0]);
            for(int i = 1; i <n ; i++){
                out.print(" " + arr[i]);
            }
        }
    }

    //T(n) = 2T(n/2)+O(n)时间复杂度 O(nlogn)
    //空间复杂度 O(n)
    public static void mergeSort1(int l, int r){
        if(l==r){
            return;
        }
        int m = (l+r) /2;
        mergeSort1(l,m);
        mergeSort1(m+1,r);
        merge(l,m,r);
    }

    //O(n)时间复杂度
    public static void merge(int l , int m, int r){
        int i = l;
        int a =l;
        int b = m+1;
        while(a<=m && b<=r){
            help[i++] = arr[a] <= arr[b] ? arr[a++]:arr[b++];
        }
        //左侧指针、右侧指针必有一个越界另一个不越界
        while(a<=m){
            help[i++] = arr[a++];
        }
        while(b<=r){
            help[i++] = arr[b++];
        }
        for(i=l;i<=r;i++){
            arr[i] = help[i];
        }
    }

非递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    ///非递归：步长从1开始每次乘2，每次拿步长多的数字进行merge
    public static void mergeSort2(){
        //时间复杂度O（nlogn）
        //空间复杂度O（n)
        for(int l,m,r,step = 1;step<n;step<<=1){
            l = 0;
            while (l<n){
                m = l+step-1;
                if(m+1>=n){
                    //已经没有右侧
                    break;
                }
                r = Math.min(l+(step<<1)-1,n-1); //l+2x-1和n-1选最小值

                //l...m m+1...r
                //             l...m m+1...r
                //                          l...m m+1...r
                merge(l,m,r);
                l = r+1;
            }
        }
    }

中序遍历

中序：左->根->右

  1. 子树头左边界进站（处理完）
  2. 栈弹出节点打印，节点右数重复步骤1）
  3. 没子树且栈空
1
2
3
4
5
6
7
8
9

    // 中序（递归）
    public static void inOrderRec(TreeNode head){
        if (head == null) return;
        inOrderRec(head.left);
        System.out.print(head.val + " ");
        inOrderRec(head.right);
    }

后序遍历

后序：左->右->根

  • 因为先序是-中左右
  • 所以先序‘是-中右左
  • 故后序是-左右中
1
2
3
4
5
6
7

    // 后序（递归）
    public static void postOrderRec(TreeNode head){
        if (head == null) return;
        postOrderRec(head.left);
        postOrderRec(head.right);
        System.out.print(head.val + " ");
    }

用栈实现遍历

先序遍历（栈）

  • 借助栈模拟：

    • 压根节点；

    • 弹出一个节点就打印；

    • 先压右子再压左子（保证左子先处理）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

    // 先序（迭代，栈）
    public static void preOrderIter(TreeNode head){
        if (head == null) { System.out.println(); return; }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()){
            TreeNode cur = stack.pop();
            System.out.print(cur.val + " ");
            if (cur.right != null) stack.push(cur.right);
            if (cur.left  != null) stack.push(cur.left);
        }
        System.out.println();
    }

中序遍历（栈）

一路左压到底：

  • 当前指针不停向左下走并入栈；
  • 左尽后，弹出栈顶打印，转向其右子树；
  • 重复 1）和 2），直到“栈空且指针为空”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

    // 中序（迭代，栈）
    public static void inOrderIter(TreeNode head){
        Stack<TreeNode> stack = new Stack<>();
        while (head != null || !stack.isEmpty()){
            if (head != null){
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                System.out.print(head.val + " ");
                head = head.right;
            }
        }
        System.out.println();
    }

后序遍历（两个栈）

利用“先序是 中左右，若改成 中右左 再逆序，就得到 左右中（后序）”。 实现：

  • stack 做“改造先序”的入栈弹栈；

  • collect 收集弹出的顺序；

  • 最后 collect 逐个弹出即为后序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    // 后序（迭代，两个栈）
    public static void postOrderTwoStacks(TreeNode head){
        if (head == null) { System.out.println(); return; }
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> collect = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()){
            TreeNode cur = stack.pop();
            collect.push(cur);
            if (cur.left  != null) stack.push(cur.left);
            if (cur.right != null) stack.push(cur.right);
        }
        while (!collect.isEmpty()){
            System.out.print(collect.pop().val + " ");
        }
        System.out.println();
    }

后序遍历（一个栈）

思路（关键是“最后访问节点”）： 维护 lastVisited：记录上一次被打印的节点。循环不变式：

  • 观察栈顶 cur：

    • 若能继续向左（左子存在且未处理过），先压左；

    • 否则若能向右（右子存在且未处理过），压右；

    • 否则（左右都没有或都处理过），打印自己并弹出，lastVisited = cur。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    // 后序（迭代，一个栈）
    public static void postOrderOneStack(TreeNode head){
        if (head == null) { System.out.println(); return; }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode lastVisited = null; // 上一次打印/访问完成的节点
        stack.push(head);
        while (!stack.isEmpty()){
            TreeNode cur = stack.peek();
            boolean goLeft  = (cur.left  != null && lastVisited != cur.left  && lastVisited != cur.right);
            boolean goRight = (cur.right != null && lastVisited != cur.right);

            if (goLeft){
                stack.push(cur.left);
            } else if (goRight){
                stack.push(cur.right);
            } else {
                System.out.print(cur.val + " ");
                lastVisited = stack.pop();
            }
        }
        System.out.println();
    }
Leetcode
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents