替代選擇排序訴選擇排序

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推出這種產品時，這對許多商業客戶來說是一個驚喜。