数据结构与算法 / 系统课时

归并排序

归并排序

归并排序先把两段分别排好,再合并为一段。下面用带排序键和原始标签的记录观察等键稳定性,同时验证空数组、奇数长度和合并区间。

学习目标

  • 识别半开区间的拆分、基例和线性合并。
  • 解释相等时先取左侧为何保持原始相对顺序。
  • 区分合并缓冲、递归栈和运行时间。

先拆分,再归并

用半开区间 [lo,hi) 表示待排序段。长度不超过 1 时直接返回。否则以 mid 分为 [lo,mid) 与 [mid,hi)。递归完成后,两侧各自有序。将当前段复制到工作缓冲,从两侧未用的首元素中选较小者写回。某一侧耗尽后,把另一侧剩余元素按原顺序写回。 MIT 归并排序资料

归并排序分解与合并过程

若比较器判定两个键相等,优先取左侧。原数组中,左侧记录本来就先于右侧记录;同一侧内部按已有顺序读取。由基例与递归归纳可知,等键记录在整个排序后仍按原先次序出现。只观察整数结果看不见稳定性,因此代码给每条记录一个独立标签。

Java 17 实现与验证

将代码保存为 MergeSortDemo.java。以有效比较器定义顺序,函数原地改写数组中的记录顺序,复用一个等长缓冲。编译命令为 javac -encoding UTF-8 --release 17 MergeSortDemo.java,运行 java MergeSortDemo。 Java Arrays 排序接口与稳定性

java
import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;

public class MergeSortDemo {
    public record Item(int key, String tag) {
        @Override
        public String toString() {
            return key + ":" + tag;
        }
    }

    public static <T> void sort(T[] values, Comparator<? super T> order) {
        Objects.requireNonNull(values, "values");
        Objects.requireNonNull(order, "order");
        if (values.length > 1) {
            sort(values, values.clone(), order, 0, values.length);
        }
    }

    private static <T> void sort(T[] values, T[] work, Comparator<? super T> order,
                                 int lo, int hi) {
        if (hi - lo < 2) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(values, work, order, lo, mid);
        sort(values, work, order, mid, hi);

        System.arraycopy(values, lo, work, lo, hi - lo);
        int left = lo;
        int right = mid;
        for (int at = lo; at < hi; at++) {
            if (right == hi || (left < mid && order.compare(work[left], work[right]) <= 0)) {
                values[at] = work[left++];
            } else {
                values[at] = work[right++];
            }
        }
    }

    public static void main(String[] args) {
        Item[] values = {new Item(4, "a"), new Item(2, "b"), new Item(4, "c"),
                         new Item(1, "d"), new Item(2, "e")};
        System.out.println("排序前: " + Arrays.toString(values));
        sort(values, Comparator.comparingInt(Item::key));
        System.out.println("排序后: " + Arrays.toString(values));
    }
}
text
排序前: [4:a, 2:b, 4:c, 1:d, 2:e]
排序后: [1:d, 2:b, 2:e, 4:a, 4:c]

成本与边界

长度为 nn 的段每次合并扫描和写入 nn 个位置。假定一次比较为常数成本,本实现即使输入已排序也执行合并。按第 4 章平分取整的层数与上下界,时间为 Θ(nlog⁡n)\Theta(n\log n)。工作缓冲占 Θ(n)\Theta(n),递归栈深度为 Θ(log⁡n)\Theta(\log n),总辅助空间为 Θ(n)\Theta(n)。本实现写回输入数组,但仍需要额外缓冲。外部排序可使用顺序合并的思想,内存和 I/O 口径需要另行分析。 MIT 排序和递推资料

本课练习

把比较器改为降序,确认键为 4 的记录仍按 a、c 顺序出现。然后把合并中的 <= 改为 <,找出能暴露等键顺序变化的最小样例。下一课比较快速排序的分区做法。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

归并排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通