A 和 B 是堆栈上的相邻运行，A 是底部和较小的运行（如果 B 较小，merge_hi 将执行合并，但同样的问题也适用于那里）。我一直试图弄清楚为什么最后一个元素A 必须大于 B 的最后一个元素，因为我看不到运行分解（或算法的其余部分）如何确保该条件。此外，在同一个函数中，代码似乎表明 B 的第一个元素总是小于 A 的第一个元素，我也不明白为什么，但我猜这个问题的答案与答案有关第一个问题。
问问题
39 次
1 回答
0
总之，疾驰就是原因。这就是为什么我们一开始没有看到它的原因，因为我认为gallop_{ left, right} 只能从merge_{ lo, hi} 调用。但事实并非如此。gallop_... 也被调用 from merge_at，在 merge_{ lo，hi} 被调用之前，为了找到“b 在哪里开始？” 和“b的结尾在哪里？”。这些调用（和后续代码）会更改 ssb（及其 length nb）和ssalength na，从而满足标题中的不变量。
也就是说，关键是 A 和 B不是在要排序的原始列表中找到的“运行堆栈上的相邻运行”。在调用merge_{ lo, hi} 之前，它们会被修剪以使标题中的条件成立。也就是说，在 A 与 B 合并之前，B 中大于 A 的最后一个元素的元素被明确排除在考虑之外。换句话说，“必须ssa.keys[na-1]在合并结束时也有那个属于”不是因为 的某些特殊属性ssa.keys[na-1]，而是因为我们以这种方式定义了“合并结束”。:-)
这也意味着当你自己实现 Timsort 时，你忽略了飞驰，你也必须忽略这里所说的优化，否则代码将无法正常工作。
于 2019-01-26T13:14:56.790 回答