1

我正在阅读 Robert Sedgewick 在 C++ 中的算法中的合并排序，并有以下问题。

static void mergeAB(ITEM[] c, int cl, ITEM[] a, int al, int ar, ITEM[] b, int bl, int br )
{ 
    int i = al, j = bl;
    for (int k = cl; k < cl+ar-al+br-bl+1; k++)
    {
        if (i > ar) { c[k] = b[j++]; continue; }
        if (j > br) { c[k] = a[i++]; continue; }
        c[k] = less(a[i], b[j]) ? a[i++] : b[j++];
    }
}

基本合并的一个值得注意的特点是，内部循环包括两个测试，以确定两个输入数组的末端是否已经到达。当然，这两个测试通常会失败，因此需要使用哨兵密钥来删除测试。也就是说，如果将一个键值大于所有其他键的元素添加到 a 和 aux 数组的末尾，则可以删除测试，因为当 a(b) 数组耗尽时，哨兵会导致从 b (a) 数组中取出 c 数组的下一个元素，直到合并完成。

但是，使用哨兵并不总是那么容易，因为可能不容易知道最大的键值，或者因为空间可能不方便。

对于合并，有一个简单的补救措施。该方法基于以下思想：鉴于我们已经习惯于复制数组以实现就地抽象，我们只需将第二个数组在复制时以相反的顺序排列（无需额外成本），以便其关联索引从右向左移动。这种排列导致最大的元素——无论它在哪个阵列中——充当另一个阵列的哨兵。

我对上述文字的问题

  1. 什么语句“当 a (b) 数组用尽时”？这里的'a（b）'是什么？

  2. 为什么作者提到确定最大键并不容易，确定最大键时空间与空间有什么关系？

  3. 作者所说的“鉴于我们不得不复制数组”是什么意思？在这种情况下辞职是什么？

  4. 要求用简单的例子来理解作为简单补救措施提到的想法？

4

2 回答 2

3

  1. “当 a (b) 数组用尽时”是“当a数组或b数组用尽时”的简写。

  2. 该接口正在处理更大数组的子数组，因此您不能简单地超出数组的末端进行写入。

  3. 该代码将数据从两个数组复制到另一个数组。由于这个副本是不可避免的，我们“被迫复制数组”意味着我们不情愿地接受必须复制数组是不可避免的。

  4. 棘手...这将需要一些时间来弄清楚是什么意思。

切线：这可能不是我编写循环的方式。我倾向于使用：

int i = al, j = bl;
for (int k = cl; i <= ar && j <= br; k++)
{
    if (a[i] < b[j])
        c[k] = a[i++];
    else
        c[k] = b[j++];
}
while (i <= ar)
    c[k++] = a[i++];
while (j <= br)
    c[k++] = b[j++];

两个尾随循环之一什么也不做。修改后的主合并循环每次迭代有 3 个测试，而一个原始算法每次迭代有 4 个测试。我没有正式测量它，但更简单的合并循环可能比原始的单循环算法更快。

前三个问题几乎最适合英语学习者。

于 2013-08-20T05:56:51.237 回答
1

a(b) 和 b(a)

有时括号用于同时表示一个或多个相似的短语：

当 a (b) 用尽时，我们从 b (a) 复制元素

方法：

当 a 用尽时，我们从 b 复制元素，当 b 用尽时，我们从 a 复制元素

哨兵有什么难的

关于哨兵的两件令人讨厌的事情是

  1. 有时您的数组数据可能包含所有可能的值，因此没有任何值可以用作哨兵，保证大于数组中的所有值
  2. 要使用哨兵而不是检查索引来查看是否完成了数组，需要在数组中有一个额外的空间来存储哨兵

辞职

我们程序员永远不会乐于复制（或移动）东西并将它们留在它们已经存在的地方，如果可能的话，更好（因为我们很懒）。在这个版本的合并排序中，我们已经放弃了尝试不复制东西的想法……我们接受了它。鉴于我们必须复制，如果我们愿意，我们可以按相反的顺序复制（当然也可以按相反的顺序使用），因为这是免费的（*）。

(*) 在这个抽象级别是免费的，在某些真正的 CPU 上的成本可能很高。几乎总是在YMMV表演领域。

于 2013-08-20T06:14:11.543 回答