排序一個巨大的數組

什麼是排序一個巨大的數組的最佳方式。說我有1G RAM，陣列是16G。什麼是最有效的方法來做到這一點？我有足夠的磁盤文件。排序一個巨大的數組

您打算使用哪種編程語言？你似乎最關心內存使用情況。虛擬內存的狀態是什麼;你甚至需要關心嗎？ *您對'最佳'*的定義是什麼？ - 時間，最小化交換或其他？ – 2011-02-24 02:37:46

@ p.campbell不是一個實際的問題。關注算法和解決方案。謝謝:) – 2011-02-24 02:38:52

@ p.campbell是啊有點。我以前遇到過另一個大文件問題。所以想出了這個。仍在爲亞馬遜採訪做準備。 LOL〜 – 2011-02-24 02:52:07

分割成塊並將512MB一次分類爲32個文件。然後將這些文件合併排序成一個文件。

2011-02-24 02:38:52 recursive

如果它是一個整數數組，你可以用一個樸素的基數排序(O(n))並且根本不使用RAM。第一個問題是「它是什麼樣的數據？」。如果它的任意數據，那麼外部mergesort可能是你最好的選擇。

-tjw

2011-02-24 03:06:33

回答