我一直在对替换选择排序进行一些研究，但在任何地方都找不到它的任何实现或替换选择排序的良好、彻底的实现！也许我看起来不够努力，但谷歌将替换选择排序与选择排序混淆了......所以这让我想知道：
选择排序和替换选择排序之间的真正区别是什么？
我在哪里可以找到替换选择排序的实现（或编写它的指南）？
替换选择排序的哪些特点使其比其他排序算法更受欢迎？
这个算法还有其他名字吗？
问问题
11693 次
2 回答
40
我以前没有看过这个算法的详细描述，我的分析基于我从阅读这组讲义中收集到的内容。
据我了解，选择排序和替换选择排序之间的主要区别在于，选择排序旨在对保存在主存中的完整序列进行排序，而替换选择排序旨在将未排序的序列转换为太大而无法放入主存的序列。可以存储在外部存储器中的一系列排序序列的“链”。然后可以将这些外部链合并在一起以形成整个排序序列。尽管它们的名称和算法操作的一两个关键步骤相似，但它们旨在解决根本不同的问题。
选择排序
网上有很多关于选择排序的好教程，所以我不会花太多时间讨论它。直观地说，该算法的工作原理如下：
- 找到最小的元素并将其交换到数组的位置 0。
- 找到第二小的元素并将其交换到数组的位置 1。
- 找到第三小的元素并将其交换到数组的位置 2
- ...
- 找到第 n 个最小的元素并将其交换到数组的第 n - 1 位。
这假设数组可以完全保存在内存中，如果是这种情况，则该算法在 Θ(n 2 ) 时间内运行。它不是很快，并且对于大型数据集是不可取的。
替换选择排序
该算法由 Donald Knuth 在 1965 年描述，因此它被设计为在与我们目前习惯的非常不同的计算环境中工作。计算机的内存很少（通常是一些固定数量的寄存器），但可以访问大型外部驱动器。构建将一些值加载到寄存器中，在那里处理它们，然后将它们直接刷新回外部存储的算法是很常见的。（有趣的是，这类似于处理器现在的工作方式，除了使用主存储器而不是外部存储）。
假设我们有足够的内存空间来保存两个数组：第一个Values大小为 n 的数组可以保存一堆值，第二个Active大小为 n 的数组保存布尔值。我们将尝试获取大量未排序值的输入流并尽最大努力对其进行排序，因为我们只有足够的内存空间来保存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
我们完成了！请注意，生成的序列未排序，但比以前好很多。它现在由按排序顺序的两条链组成。将它们合并在一起（与我们为 mergesort 进行合并的方式相同）将对结果数组进行排序。这个算法可能会产生更多的链，但由于我们的样本输入很小，我们只有两个。
那么这有多快呢？好吧，循环的每次迭代总共最多进行 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.
如果现在有任何理由编写这个算法，我会感到震惊。几十年前，当内存非常非常小的时候，这是有道理的。如今，有更好的外部排序算法可用，它们几乎肯定会胜过这个算法。
希望这可以帮助！
于 2013-05-02T04:24:20.233 回答
0
替换排序仍然用于外部排序，因为它将产生最少数量的要合并的字符串，而合并是排序中成本最高的部分。使用的方法比提供的优秀示例 templatetypedef 稍微复杂一些，但基本上它缓冲许多记录，对它们进行排序，收集像 -1 1 等无序记录并将它们保存在缓冲区中，写出低阶部分序列，填充空的空间，再次排序，从缓冲区合并任何适合的记录，并重复直到序列不能继续，然后它转储序列，从序列记录和新的输入记录中取出缓冲，从下一个字符串开始。重复到输入结束。
在一些应用程序中，不需要合并，因为替换排序会从序列记录中扫出，然后稍后将它们重新插入正确的位置。1964 年霍尼韦尔和 IBM 推出这种类型时，这让许多商业客户感到惊讶。
于 2016-11-30T01:30:29.117 回答