algorithm - 如何摆脱合并排序中的哨兵？

Question

我知道哨兵的使用在某种程度上等同于零填充（在复杂性的意义上）。

对于那些不知道什么是零填充的人：

我们附加了许多零（或其他一些值，没关系）以使大小为 2 的幂，并且在应用归并排序算法之后，我们消除了那些附加的零。

但是，除了零填充之外，还有其他方法可以摆脱哨兵吗？

Answer 1

您混淆了两个不相关的概念。它们并不接近等效。哨兵是放置在列表（逻辑）末尾的额外元素。

它故意具有一些“限制”值，该值允许通常停止遍历数组的测试也停止在数组末端的遍历。

例如，如果我们在列表 [1, 8, 4, 7] 中查找值大于 5 的第一个元素，并且没有标记，那么算法将是：

i = 0; 
while i < 4 { if a[i] > 5 return i; i = i + 1 }
return "not found"

我们将继续添加一个大于 5 的元素，比如 6. [1, 8, 4, 7, 6]。现在搜索变成

i = 0;
while a[i] <= 5 { i = i + 1 }
return if i < 4 then i else "not found"

请注意，第二个代码每次迭代都有一个比较。第一个有两个。这就是哨兵的原因。它们允许较少的比较。

所以你不想“摆脱”哨兵。它们是使循环运行得更快的工具。它们仅适用于某些情况。当您遇到其中一种情况时，它们是一个有用的选择。

另一方面，零填充通常用于使递归分治算法更简单。快速傅里叶变换就是一个例子。对于长度为 2^n 的输入，它有一个非常简单的实现。虽然存在其他大小数据的算法，但它们要复杂得多。因此，将数据补零到下一个 2 的幂大小是很常见的。

所以你也不想摆脱零填充。这只是一个实现选项。

哨兵和航空填充都不适用于合并排序。