数据结构与算法 / 系统课时
归并排序
归并排序
归并排序先把两段分别排好,再合并为一段。下面用带排序键和原始标签的记录观察等键稳定性,同时验证空数组、奇数长度和合并区间。
学习目标
- 识别半开区间的拆分、基例和线性合并。
- 解释相等时先取左侧为何保持原始相对顺序。
- 区分合并缓冲、递归栈和运行时间。
先拆分,再归并
用半开区间 [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]成本与边界
长度为 的段每次合并扫描和写入 个位置。假定一次比较为常数成本,本实现即使输入已排序也执行合并。按第 4 章平分取整的层数与上下界,时间为 。工作缓冲占 ,递归栈深度为 ,总辅助空间为 。本实现写回输入数组,但仍需要额外缓冲。外部排序可使用顺序合并的思想,内存和 I/O 口径需要另行分析。 MIT 排序和递推资料
本课练习
把比较器改为降序,确认键为 4 的记录仍按 a、c 顺序出现。然后把合并中的 <= 改为 <,找出能暴露等键顺序变化的最小样例。下一课比较快速排序的分区做法。
按自己的节奏,确认真正理解。