替代选择排序诉选择排序 [英] Replacement Selection Sort v. Selection Sort
问题描述
我一直在做关于更换选择排序的一些研究，我找不到它或任何实现了良好的，全面的实施替代选择排序的任何地方！也许我不看够硬，但谷歌是混淆替代选择排序与选择排序......所以这让我疑惑：
I've been doing some research on replacement selection sort, and I can't find any implementations of it or a good, thorough implementation of replacement selection sort anywhere! Maybe I'm not looking hard enough, but Google is confusing replacement selection sort with selection sort... so this got me wondering:
什么是选择排序和替换选择排序之间的真正区别是什么？
What are the real differences between selection sort and replacement selection sort?
我在哪里可以找到替代选择排序的实现（或引导来写的话）？
Where can I find an implementation of replacement selection sort (or a guide to write it)?
什么是替代选择的特点那种使它比其他的排序算法更可取？
What are the characteristics of replacement selection sort that make it more desirable than other sorting algorithms?
这是算法的任何其他名字知道？
Is this algorithm known by any other names?
推荐答案
我还没有看到这种算法描述的细节之前，和AM情况下，我分析我所收集的从阅读的this的讲义的。
I have not seen this algorithm described in much detail before, and am basis my analysis on what I have gathered from reading this set of lecture notes.
根据我的理解，选择排序和替代选择排序之间的主要区别在于，选择排序是设计来排序在主内存中保存一个完整的序列，而替代选择排序是设计来转换一个未排序的序列太大，不适合到主存储器成一系列可被存储在外部存储器排序序列的链的。这些外部绳股可以被合并在一起，以形成整体的排序序列。尽管相似在他们的名字，并且在该算法的操作的一个或两个关键步骤，它们被设计用来解决根本不同的问题。
By my understanding, the key difference between selection sort and replacement selection sort is that selection sort is designed to sort a complete sequence held in main memory, while replacement selection sort is designed to convert an unsorted sequence too large to fit into main memory into a series of "strands" of sorted sequences that can be stored in external memory. These external strands can then be merged together to form the overall sorted sequence. Despite the similarity in their name and in one or two key steps in the operation of the algorithm, they're designed to solve fundamentally different problems.
有上选择排序网上提供很多很好的教程，所以我不会花太多时间讨论这个问题。直观地说，该算法的工作方式如下：
There are many good tutorials on selection sort available online, so I won't spend too much time discussing it. Intuitively, the algorithm works as follows:
- 找到最小的元素，将其交换阵列的位置0。
- 找到的第二小的元素，将其交换到位置1的阵列中。
- 找到第三最小的元素，将其交换到位置2数组 的
- ...
- 找到第n个最小元素，并将其交换到N位置时 - 数组的1
这假设数组可以完全在内存中举行，如果是这样的情况下，这个算法的运行和西塔（N 2 ）的时间。这不是非常快，而对于大型数据集是不可取的。
This assumes that the array can be held completely in memory, and if that's the case this algorithm runs in Θ(n2) time. It's not very fast, and for large data sets is not advisable.
这个算法是在1965年描述的高德纳，所以它的设计在一个非常不同的计算环境比我们目前使用的一个工作。计算机有很少的内存（通常情况下，一些固定的寄存器数），但有机会获得较大的外部驱动器。这是常见的建立算法，将加载一些值到寄存器，处理他们在那里，然后刷新它们直接返回到外部存储。 （有趣的是，这是类似于如何工作的处理器，现在，除了与主内存，而不是外部存储）。
This algorithm was described in 1965 by Donald Knuth, so it's designed to work in a very different computing environment than the one we're currently used to. Computers have very little memory (usually, some fixed number of registers), but have access to large external drives. It's common to build algorithms that would load some values into registers, process them there, then flush them directly back to the external storage. (Interestingly, this is similar to how processors work right now, except with main memory instead of external storage).
假设我们有足够的内存空间来容纳两个数组：第一阵列值大小为n，可容纳一堆数值，以及第二阵列活动的大小N保存布尔值。我们要尽量采取无序值的大的输入流，尽我们所能的工作来排序，因为我们只有有足够的空间在内存中保存有效和值阵列，加上存储空间一些额外的变量。
Let's assume that we have enough space in memory to hold two arrays: a first array Values of size n that can hold a bunch of values, and a second array Active of size n that holds boolean values. We're going to try to take a large input stream of unsorted values and do our best job to sort it, given that we only have enough room in memory to hold the Active and Values arrays, plus a few extra variables for storage space.
该算法背后的想法是如下。首先，负载直接包含未排序的顺序进值。然后，将所有的值阵列外源氮有效值真。例如，如果 N = 4 ，我们可能有这样的设置：
The idea behind the algorithm is as follows. First, load n values from the external source containing the unsorted sequence directly into the Values array. Then, set all of the Active values to true. For example, if n = 4, we might have this setup:
Values: 4 1 0 3
Active: Yes Yes Yes Yes
替换选择排序算法通过反复寻找的值数组中的最低值，写出来的输出流。在这种情况下，我们通过找到0值，并将其写入到该流开始。这给了
The replacement selection sort algorithm works by repeatedly looking for the lowest value in the Values array and writing it out to the output stream. In this case, we start off by finding the 0 value and writing it to the stream. This gives
Values: 4 1 3
Active: Yes Yes Yes Yes
Output: 0
现在，我们已经在我们的值阵列中的空白点，所以我们可以从外部源拉另一个值。让我们假设，我们得到2。在这种情况下，我们有这个设置：
Now, we have a blank spot in our Values array, so we can pull another value in from the external source. Let's suppose that we get 2. In that case, we have this setup:
Values: 4 1 2 3
Active: Yes Yes Yes Yes
Output: 0
注意，由于2> 0和0是这里最小的元素，我们保证，当我们写了0到输出，2个不应该来之前。那很好。因此，我们继续该算法的下一个步骤，并再次找到最小的元素这里。那是1，因此，我们将其发送到输出设备：
Notice that since 2 > 0 and 0 was the smallest element here, we're guaranteed that when we wrote out the 0 to the output, the 2 shouldn't have come before it. That's good. Therefore, we go on to the next step of the algorithm and again find the smallest element here. That's the 1, so we send it to the output device:
Values: 4 2 3
Active: Yes Yes Yes Yes
Output: 0 1
现在，读取从外部源另一个值：
Now, read in another value from the external source:
Values: 4 -1 2 3
Active: Yes Yes Yes Yes
Output: 0 1
现在，我们就麻烦了。这个新的值（-1），比1时，这意味着如果我们真的希望这个值进入的有序输出，它应该在1。但是之前，我们没有足够的内存从重读输出设备，并确定了。相反，我们要做到以下几点。现在，让我们保持在-1在内存中。我们将尽我们所能，剩下的元素进行排序，但是，当我们完成这样做，我们会做一个的第二的迭代产生一个排序的序列，并把-1成该序列。换句话说，而不是产生一种排序顺序，我们将产生两个。
Now we're in trouble. This new value (-1) is lower than the 1, meaning that if we truly wanted this value to go into the output in sorted order, it should come before the 1. However, we don't have enough memory to reread from the output device and fix it up. Instead, we're going to do the following. For now, let's keep the -1 in memory. We're going to do our best to sort the remaining elements, but when we're done doing so, we'll do a second iteration of generating a sorted sequence, and will put the -1 into that sequence. In other words, instead of producing one sorted sequence, we're going to produce two.
要表明，我们不希望写出-1然而，我们要纪念插槽控股-1为无效的记忆。这是如下所示：
To indicate in memory that we don't want to write out the -1 yet, we're going to mark the slot holding -1 as inactive. This is shown here:
Values: 4 -1 2 3
Active: Yes NO Yes Yes
Output: 0 1
从现在开始，我们只pretend该-1不在这里。
From now on, we'll just pretend that the -1 isn't here.
让我们继续前进。我们现在发现内存中仍然有效（2）最小的值，并写入到设备：
Let's continue onward. We now find the smallest value in memory that is still active (2), and write it out to the device:
Values: 4 -1 3
Active: Yes NO Yes Yes
Output: 0 1 2
我们现在拉从输入装置的下一个值。让我们假设这是7：
We now pull the next value from the input device. Let's suppose it's 7:
Values: 4 -1 7 3
Active: Yes NO Yes Yes
Output: 0 1 2
由于7> 2，谈到在输出2后，所以我们没有做任何事情。
Since 7 > 2, it comes after the 2 in the output, so we don't do anything.
在接下来的迭代中，我们发现了最低的工作值（3），并把它写的：
On the next iteration, we find the lowest active value (3) and write it out:
Values: 4 -1 7
Active: Yes NO Yes Yes
Output: 0 1 2 3
我们拉从输入装置的下一个值。让我们假设它的也的3。在这种情况下，我们知道，因为3是最小的值，我们可以只写它直接到输出流，因为3是最小的所有值这里，我们可以自救迭代：
We pull the next value from the input device. Let's suppose it's also 3. In this case, we know that since 3 is the smallest value, we can just write it directly to the output stream, since 3 is the smallest of all the values here and we can save ourselves an iteration:
Values: 4 -1 7
Active: Yes NO Yes Yes
Output: 0 1 2 3 3
我们现在拉从输入装置的下一个值。想这是2.在这种情况下，如前所述，我们知道，2应当出现在3就像前面-1之前，这意味着我们需要保持2在存储器中用于现在;我们将它写出来以后。现在，我们的设置是这样的：
We now pull the next value from the input device. Suppose it's 2. In that case, as before, we know that the 2 should come before the 3. Just like the earlier -1, this means that we need to hold the 2 in memory for now; we'll write it out later on. Now our setup looks like this:
Values: 4 -1 7 2
Active: Yes NO Yes NO
Output: 0 1 2 3 3
现在，我们找到最小的活动值（4），并将其写入到输出设备：
Now, we find the smallest active value (4) and write it to the output device:
Values: -1 7 2
Active: Yes NO Yes NO
Output: 0 1 2 3 3 4
假设我们现在读到的1作为我们的下一个输入。因此，我们把它放到值，但将其标记为不活动：
Suppose we now read in a 1 as our next input. We therefore put it into Values, but mark it inactive:
Values: 1 -1 7 2
Active: NO NO Yes NO
Output: 0 1 2 3 3 4
只有一个活动的价值，这是7，所以我们写出来：
There's only one active value, which is 7, so we write it out:
Values: 1 -1 2
Active: NO NO Yes NO
Output: 0 1 2 3 3 4 7
让我们假设我们现在读5。在这种情况下，像以前一样，我们店，但时隙标记不活动：
Let's suppose we now read a 5. In that case, as before, we store it but mark the slot inactive:
Values: 1 -1 5 2
Active: NO NO NO NO
Output: 0 1 2 3 3 4 7
注意的所有的值现在是无效的。这意味着我们已经从内存中所有可以进入的电流输出的运行值冲出。现在，我们需要去写出所有我们抱着为后来的值。要做到这一点，我们纪念所有的数值为活动，然后重复以前一样：
Notice that all the values are now inactive. This means that we've flushed out from memory all the values that can go into the current output run. Now, we need to go and write out all of the values we were holding for later. To do this, we mark all the values as active, then repeat as before:
Values: 1 -1 5 2
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7
-1是最小的值，所以我们把它输出：
-1 is the smallest value, so we output it:
Values: 1 5 2
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7 -1
假设我们读了3 -1 LT; 3，所以我们把它加载到值阵列。
Values: 1 3 5 2
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7 -1
1是最小的价值在这里，所以我们将其删除：
1 is the smallest value here, so we remove it:
Values: 3 5 2
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7 -1 1
让我们假设，我们现在在外面的输入值。我们将纪念这个插槽中完成的：
Let's suppose that we're now out of input values. We'll mark this slot as done:
Values: --- 3 5 2
Active: Yes Yes Yes Yes
Output: 0 1 2 3 3 4 7 -1 1
2随之而来的：
2 comes next:
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
和我们就大功告成了！需要注意的是结果序列是的没有的排序，但它的很多比以前更好。现在由两股是按照排序顺序。合并在一起（以同样的方式，我们会做的归并合并）将排序结果数组。这种算法可能已经产生了更多的股，但由于我们的样本投入很小，我们只有两个。
And we're done! Note that the resulting sequence is not sorted, but it's a lot better than before. It now consists of two strands that are in sorted order. Merging them together (in the same way we'd do a merge for mergesort) will sort the resulting array. This algorithm could potentially have produced far more strands, but since our sample input was small, we only had two.
那么，如何快速呢？井，该循环的每次迭代确实总共最多n比较（在存储器中），一个读，和一个写。因此，如果有N个总价值流中，算法确实O（NN）的比较和O（N）内存操作。如果内存操作是昂贵的，这是不是太糟糕，但你需要一个二传在年底合并一切重新走到一起。
So how fast is this? Well, each iteration of the loop does a total of at most n comparisons (in memory), one read, and one write. Thus if there are N total values in the stream, the algorithm does O(nN) comparisons and O(N) memory operations. If memory operations are expensive, this isn't too bad, though you'll need a second pass at the end to merge everything back together.
在伪code，该算法是这样的：
In pseudocode, the algorithm looks like this:
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.
我会如果有任何理由code算法了，现在感到震惊。这是有道理的几十年前，当内存真的，真的非常小。如今，有更好的外部排序算法的可用，他们会几乎肯定胜过这个算法。
I would be shocked if there was any reason to code this algorithm up now. This made sense many decades ago when memory was really, really small. Nowadays, there are far better external sorting algorithms available, and they'd almost certainly outperform this algorithm.
希望这有助于！
这篇关于替代选择排序诉选择排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
