爲O整數的外部排序（N日誌N）的讀取和O（N）寫道：

Question

我感興趣的算法，我應該使用O(N log N)讀取，滿足int對外排序的要求和O(N)寫

Answer 1

如果該類型排序（其中數據不能全部放入到核心在一次）的算法後的時候，我的解決方案來自於「革命」，當高端機器具有非常初期內存比大多數現代計算器少。我還沒有制定出大O屬性，但我認爲這將是O（n）讀取，O（n日誌n）排序階段（取決於所選的排序方法）和O（n）寫入。

比方說，你的數據集有一個百萬個元素，你只可以在內存中同時滿足10萬人。以下是我要做的：

• 在第一個100,000中讀取，對它們進行排序並將其重新寫入排序列表。
• 爲每組100,000個做這個。
• 對10個組運行合併操作。

換句話說，一旦你的10個組在組內排序，從每個組抓取第一個條目。

然後寫該最低那些10的（這是最低的整個百萬的）輸出到輸出文件，並讀出從在其位置該組的下一個。

然後就繼續選擇最低的10，寫出來，並從同一組替換它。通過這種方式，最終的輸出是整個一百萬個條目的排序列表。

Answer 2

嘗試此頁：Sorting Algorithms。除了展示幾種算法的漂亮動畫之外，它還解釋了它們如何工作以及它們的複雜性。

Answer 3

退房external merge sort算法。