algorithm - 替换选择排序与选择排序

Question

我一直在做一些关于替换选择排序的研究，但我找不到它的任何实现或任何地方的替换选择排序的良好、彻底的实现!也许我看起来不够努力，但谷歌将替换选择排序与选择排序混淆了......所以这让我想知道:

选择排序和替换选择排序之间的真正区别是什么？

我在哪里可以找到替换选择排序的实现(或编写它的指南)？

替换选择排序的哪些特点使其比其他排序算法更受欢迎？

这个算法还有其他名字吗？

Answer 1

我之前没有详细了解过这个算法，我的分析基于我从阅读 this set of lecture notes 中收集到的信息。 .

根据我的理解，选择排序和替换选择排序之间的主要区别在于，选择排序旨在对保存在主内存中的完整序列进行排序，而替换选择排序旨在将太大而无法放入主内存的未排序序列转换为可以存储在外部存储器中的一系列已排序序列的“链”。然后可以将这些外部链合并在一起以形成整体排序序列。尽管它们的名称和算法操作中的一两个关键步骤相似，但它们旨在解决根本不同的问题。

选择排序

网上有很多关于选择排序的好教程，所以我不会花太多时间讨论它。直观地，该算法的工作原理如下:

找到最小的元素并将其交换到数组的位置 0。

找到第二小的元素并将其交换到数组的位置 1。

找到第三小的元素并将其交换到数组的位置 2

...

找到第 n 个最小元素并将其交换到数组的位置 n - 1。

这假设数组可以完全保存在内存中，如果是这种情况，则该算法在 Θ(n2) 时间内运行。它不是很快，对于大型数据集是不可取的。

替换选择排序

该算法由 Donald Knuth 于 1965 年描述，因此它设计用于在与我们目前使用的计算环境截然不同的计算环境中工作。计算机的内存很少(通常是一些固定数量的寄存器)，但可以访问大型外部驱动器。构建将一些值加载到寄存器中，在那里处理它们，然后将它们直接刷新回外部存储的算法是很常见的。 (有趣的是，这类似于处理器现在的工作方式，除了主存储器而不是外部存储器)。

假设我们有足够的内存空间来保存两个数组:第一个数组 Values大小为 n 的可以容纳一堆值，以及第二个数组 Active大小为 n 的，包含 bool 值。我们将尝试获取大量未排序值的输入流并尽最大努力对其进行排序，因为我们只有足够的内存空间来容纳 Active和 Values数组，加上一些额外的存储空间变量。

该算法背后的思想如下。一、加载n来自包含未排序序列的外部源的值直接进入 Values大批。然后，设置所有 Active值为 true .例如，如果 n = 4 ，我们可能有这样的设置:

Values:    4    1    0    3
Active:    Yes  Yes  Yes  Yes

替换选择排序算法通过重复查找 Values 中的最小值来工作。数组并将其写入输出流。在这种情况下，我们首先找到 0 值并将其写入流。这给

Values:    4    1         3
Active:    Yes  Yes  Yes  Yes

Output:    0

现在，我们的 Values 中有一个空白点。数组，因此我们可以从外部源中提取另一个值。假设我们得到 2。在这种情况下，我们有以下设置:

Values:    4    1    2    3
Active:    Yes  Yes  Yes  Yes

Output:    0

请注意，由于 2 > 0 并且 0 是此处的最小元素，因此我们可以保证，当我们将 0 写出到输出时，2 不应该出现在它之前。那挺好的。因此，我们继续算法的下一步，再次在这里找到最小元素。那是 1，所以我们将它发送到输出设备:

Values:    4         2    3
Active:    Yes  Yes  Yes  Yes

Output:    0  1

现在，从外部源读取另一个值:

Values:    4    -1   2    3
Active:    Yes  Yes  Yes  Yes

Output:    0  1

现在我们遇到了麻烦。这个新值 (-1) 小于 1，这意味着如果我们真的希望这个值按排序顺序进入输出，它应该在 1 之前。但是，我们没有足够的内存来重新读取输出设备并修复它。相反，我们将执行以下操作。现在，让我们将 -1 保留在内存中。我们将尽最大努力对剩余元素进行排序，但是当我们这样做时，我们将进行第二次迭代以生成已排序的序列，并将 -1 放入该序列中。换句话说，我们将生成两个，而不是生成一个已排序的序列。

为了在内存中表明我们还不想写出 -1，我们将把持有 -1 的插槽标记为非事件状态。这在这里显示:

Values:    4    -1   2    3
Active:    Yes  NO   Yes  Yes

Output:    0  1

从现在开始，我们就假装 -1 不在这里。

让我们继续前进。我们现在找到内存中仍处于事件状态的最小值 (2)，并将其写入设备:

Values:    4    -1        3
Active:    Yes  NO   Yes  Yes

Output:    0  1  2

我们现在从输入设备中提取下一个值。让我们假设它是 7:

Values:    4    -1   7    3
Active:    Yes  NO   Yes  Yes

Output:    0  1  2

由于 7 > 2，它在输出中的 2 之后，所以我们什么都不做。

在下一次迭代中，我们找到最低的事件值 (3) 并将其写出:

Values:    4    -1   7    
Active:    Yes  NO   Yes  Yes

Output:    0  1  2  3

我们从输入设备中提取下一个值。让我们假设它也是 3。在这种情况下，我们知道因为 3 是最小值，我们可以直接将它写入输出流，因为 3 是这里所有值中的最小值，我们可以节省一次迭代:

Values:    4    -1   7    
Active:    Yes  NO   Yes  Yes

Output:    0  1  2  3  3

我们现在从输入设备中提取下一个值。假设它是 2。在那种情况下，和以前一样，我们知道 2 应该在 3 之前。就像前面的 -1 一样，这意味着我们现在需要将 2 保存在内存中；我们稍后会写出来。现在我们的设置看起来像这样:

Values:    4    -1   7    2
Active:    Yes  NO   Yes  NO

Output:    0  1  2  3  3

现在，我们找到最小的事件值 (4) 并将其写入输出设备:

Values:         -1   7    2
Active:    Yes  NO   Yes  NO

Output:    0  1  2  3  3  4

假设我们现在读入 1 作为我们的下一个输入。因此我们将其放入 Values ，但将其标记为非事件:

Values:    1    -1   7    2
Active:    NO   NO   Yes  NO

Output:    0  1  2  3  3  4

只有一个有效值，即 7，因此我们将其写出:

Values:    1    -1        2
Active:    NO   NO   Yes  NO

Output:    0  1  2  3  3  4  7

假设我们现在读取一个 5。在这种情况下，和以前一样，我们存储它但将插槽标记为非事件:

Values:    1    -1   5    2
Active:    NO   NO   NO   NO

Output:    0  1  2  3  3  4  7

请注意，所有值现在都处于非事件状态。这意味着我们已经从内存中清除了所有可以进入当前输出运行的值。现在，我们需要去写出我们为以后持有的所有值。为此，我们将所有值标记为事件值，然后像以前一样重复:

Values:    1    -1   5    2
Active:    Yes  Yes  Yes  Yes

Output:    0  1  2  3  3  4  7

-1 是最小值，所以我们输出它:

Values:    1         5    2
Active:    Yes  Yes  Yes  Yes

Output:    0  1  2  3  3  4  7  -1

假设我们读到一个 3。-1 < 3，所以我们把它加载到 Values 中大批。

Values:    1    3    5    2
Active:    Yes  Yes  Yes  Yes

Output:    0  1  2  3  3  4  7 -1

1 是这里的最小值，因此我们将其删除:

Values:         3    5    2
Active:    Yes  Yes  Yes  Yes

Output:    0  1  2  3  3  4  7 -1  1

假设我们现在没有输入值。我们会将此插槽标记为已完成:

Values:    ---  3    5    2
Active:    Yes  Yes  Yes  Yes

Output:    0  1  2  3  3  4  7 -1  1

接下来是2:

Values:    ---  3    5    ---
Active:    Yes  Yes  Yes  Yes

Output:    0  1  2  3  3  4  7 -1  1  2

然后3:

Values:    ---  ---  5    ---
Active:    Yes  Yes  Yes  Yes

Output:    0  1  2  3  3  4  7 -1  1  2  3

最后，5:

Values:    ---  ---  ---  ---
Active:    Yes  Yes  Yes  Yes

Output:    0  1  2  3  3  4  7 -1  1  2  3  5

我们完成了!请注意，结果序列没有排序，但比以前好很多。它现在由按顺序排列的两条链组成。将它们合并在一起(与我们为合并排序进行合并的方式相同)将对结果数组进行排序。这个算法可能会产生更多的链，但由于我们的样本输入很小，我们只有两个。

那么这有多快？好吧，循环的每次迭代总共最多进行 n 次比较(在内存中)、一次读取和一次写入。因此，如果流中有 N 个总计值，则该算法执行 O(nN) 次比较和 O(N) 次内存操作。如果内存操作很昂贵，这还不算太糟糕，但您需要在最后进行第二遍才能将所有内容重新合并在一起。

在伪代码中，算法如下所示:

Make Values an array of n elements.
Make Active an array of n booleans, all initially true.

Read n values from memory into Values.
Until no values are left to process:
    Find the smallest value that is still active.
    Write it to the output device.
    Read from the input device into the slot where the old element was.
    If it was smaller than the old element, mark the old slot inactive.
    If all slots are inactive, mark them all active.

如果现在有任何理由对这个算法进行编码，我会感到震惊。几十年前，当内存非常非常小时，这是有道理的。如今，有更好的external sorting algorithms可用，而且它们几乎肯定会胜过这个算法。

希望这可以帮助!