替代选择排序诉选择排序

Question

我一直在做关于更换选择排序的一些研究，我找不到它的任何实现还是不错的，贯彻执行更换选择的排序任何地方！也许我不看够硬，但谷歌是混淆替代选择排序与选择排序......所以这让我疑惑：

什么是选择排序和替换选择排序之间的差异？

我在哪里可以找到替代选择排序（或写一个指南）的实现？

有什么替代选择的特征排序，使它比其他的排序算法更可取？

这是算法由任何其他名称为人所知？

Answer 1

我还没有看到这个算法之前，很多细节描述，以及根据上午我分析我从读this set of lecture notes聚集。

按照我的理解，选择排序和替换选择排序之间的关键区别在于，选择排序的目的是对存储在主存储器中的完整序列进行排序，而置换选择排序的目的是将未排序的序列转换得太大而不适合主存储器分成一系列可以存储在外部存储器中的分类序列的“链”。这些外部股可以合并在一起形成整个排序序列。尽管它们的名称和操作算法的一个或两个关键步骤相似，但它们旨在解决根本不同的问题。

选择排序

上有选择排序网上提供很多很好的教程，所以我不会花太多时间讨论这个问题。直观上，算法的工作原理如下：

• 找到最小的元素并将其交换到数组的位置0。
• 查找第二小元素并将其交换到数组的第1位。
• 查找第三最小的元素和交换它来定位该阵列
• 的2 ...
• 查找第n个最小元件和交换它位置n - 1阵列的。

这假定该阵列可以完全在内存中保持，并且如果是这样的情况下，这算法Θ（N ）时运行。这不是很快，对于大型数据集是不可取的。

替代选择排序

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

假设，我们在内存足够的空间容纳两个数组：大小为n的第一阵列Values，可容纳一堆数值，以及大小n保存布尔值的第二阵列Active。我们将尝试采用大量未排序值的输入流，并尽最大努力对其进行排序，因为我们只有足够的空间容纳Active和Values阵列，并且还有一些额外的存储空间变量。

算法背后的思想如下。首先，将包含未排序序列的外部数据源的值直接加载到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. 

我会感到震惊，如果有任何理由现在编写这种算法了。这在数十年前就已经有了意义，当时记忆真的很小。现在，有更好的external sorting algorithms可用，他们几乎肯定会胜过这个算法。

希望这会有所帮助！

Answer 2

替换排序仍用于外部排序，因为它会产生最小数量的字符串进行合并，合并是排序中成本最高的部分。所使用的方法比提供的优秀示例templatetypedef复杂一点，但基本上它缓存了许多记录，对它们进行排序，收集诸如-1 1等之外的序列记录并将它们保存在缓冲区中，写出低位部分，填充空的空间，再次排序，从缓冲区合并任何适合的记录，并且重复直到序列不能继续，然后它转储序列，将缓冲出的序列记录和新的输入记录，从下一个字符串开始。重复输入结束。

在一些应用程序中，不需要合并，因为替换排序将序列记录扫出，然后将它们重新插入到正确的位置。 1964年，当霍尼韦尔和IBM推出这种产品时，这对许多商业客户来说是一个惊喜。