這些數字在每個檔案中和所有檔案中都是唯一的。這是當我們的計算機無法存盤所有資料時將 n 個檔案合并為一個已排序檔案的一種流行方法（外部排序）：
- 對每個較小的檔案進行排序
- 從每個檔案中讀取第一個元素
- 創建堆
- 而堆不為空：
- 將最小元素寫入最終檔案
- 將較小檔案（其元素在上面的步驟中寫入主檔案）中的下一個元素插入到堆中
雖然我確實理解這個演算法如何幫助記憶體使用 - 涉及很多 I/O 開銷。
另一種可能的方法使用桶排序 - 特別是如果數字均勻分布：
- 創建 n 個存盤桶 - (max_num-min_number)/number_of_elements_in_1_bucket
- 對于每個較小的檔案：
- 讀取檔案
- 創建批量更新字典 {bucket_number:[元素串列]}
- 將上述字典中的資料附加到相應的存盤桶檔案中
- 字典空間有限，因此每個較小的檔案一次只能處理 100 個元素。因此重復以上 2 個步驟，直到我們用完當前檔案元素
- 對于創建的每個存盤桶檔案
- 對每個桶中的資料進行排序
- 將所有檔案附加到一個排序檔案中
現在，我相信后一種方法在時間復雜度方面可以稍微快一點或至少相當，但會為臨時檔案使用更多的存盤空間。這兩種方法在時間復雜度上是否具有可比性，還是即使經過多次 I/O 呼叫，第一種方法也總是更好？我是否在第二種方法中遺漏了一些耗時的步驟，使其不太理想？
uj5u.com熱心網友回復：
我的理解是相反。如果數字在可預測范圍內具有可預測的分布，則桶排序會更快。（在限制O(n)與O(n log(n))基于比較的排序中。）更好的是，桶可以相互獨立排序。這使得它們非常適合分布式排序。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/327571.html
上一篇：生成圖邊的高效演算法
下一篇：有無Babel的Vue專案？