c++多路歸并

• 多路歸并
• k的選擇
• 優化

多路歸并

外部排序最常用的算法：將原文件分解成多個能夠一次性裝入內存的部分，分別把每一部分調入內存完成排序。然后，對已經排序的子文件進行歸并排序**

k的選擇

假設總共m個子文件，每次歸并k個子文件，那么一共需要歸并 次（掃描磁盤），在k個元素中找出最小值（或最大值）需要比較k-1次。如果總記錄數為N，所以時間復雜度就是 ， 由于 隨k的增大而增大，所以比較次數的增加會逐步抵消“低掃描次數”帶來的性能增益，所以對于k值的選擇，主要涉及兩個問題：
?每一輪歸并會將結果寫回到磁盤，那么k越小，磁盤與內存之間數據的傳輸就會越多，增大k可以較少掃描次數
?k個元素中選取最小的元素需要比較k-1次，如果k越大，比較的次數就會越大

優化

可以利用下列方法減少比較次數：
?敗者樹
?建堆：使用一個k個元素的數組，第一次將k個文件中最小的元素讀入數組（并且記錄每個元素來自哪個文件），然后建最小堆，將堆頂元素刪除，并從堆頂元素的源文件中取出下一個數，插入堆中，調整后重復上述操作。雖然第一次需要遍歷k個文件取出最小元素，加上建堆需要一定時間，但是后續操作可以很快完成

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的c++多路归并的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。