为什么归并排序稳定：相等键不换位
合并时相等取左侧，原序靠前的相等键先出，稳定性由此而来。
稳定性 = 相等键的原始相对顺序在排序后不变。归并排序靠合并规则保证它。
图：归并合并“相等取左侧”保证稳定
# 左 L=[2,4,5,6]，右 R=[1,2,3,8]，两个 2 分别记为 2_前、2_后
# 合并到 temp：先遇到 L 的 2_前 与 R 的 2_后 相等
# 规则：相等取左侧 L → 2_前 先写入 → 2_后 随后
# 结果中 2_前 仍在 2_后 之前，稳定成立
对比快排：partition 会跨位置交换，相等键顺序被打乱，故快排不稳定。归并的“相等取左侧”是它比快排更适合按多字段排序的原因。
相关推荐：归并排序为什么稳 · 三种 O(n²) 排序对比
评论 (0)
正文划词可点「问萝卜特」——自动发评论并由 AI 回复
加载评论中…