外部排序實現使用堆來生成若干個順串，然后使用多路歸并算法來生成最終排序好的內容。
本來打算使用敗者樹，結果發現敗者樹當參與的競賽者相對較多的情況下，沒有全部完成就被空節點充滿了。
這個按照它的嚴格算法，其實也是可以知道不能保證總是能排完的。天快亮了，才徹底放棄使用敗者樹。改成實現贏者樹，結果發現贏者樹能保證不出錯，實現竟也順手。
最后整了個測試文件500M的隨機內容，2~3分鐘排序完成了（應該還可以優化），感覺還行。
代碼較多，最要考慮到以后可能要重用。
package algorithms.extsort;
import java.io.IOException;
import algorithms.MinHeap;
/**
* @author yovn
*
*/
public class ExternalSorter {
public void sort(int heapSize,RecordStore source,RunAcceptor mediator ,ResultAcceptor ra)throws IOException
{
MinHeap<Record> heap=new MinHeap<Record>(Record.class,heapSize);
for(int i=0;i<heapSize;i++)
{
Record r=source.readNextRecord();
if(r.isNull())break;
heap.insert(r);
}
Record readR=source.readNextRecord();
while(!readR.isNull()||!heap.isEmpty())
{
Record curR=null;
//begin output one run
mediator.startNewRun();
while(!heap.isEmpty())
{
curR=heap.removeMin();
mediator.acceptRecord(curR);
if (!readR.isNull()) {
if (readR.compareTo(curR) < 0) {
heap.addToTail(readR);
} else
heap.insert(readR);
}
readR=source.readNextRecord();
}
//done one run
mediator.closeRun();
//prepare for next run
heap.reverse();
while(!heap.isFull()&&!readR.isNull())
{
heap.insert(readR);
readR=source.readNextRecord();
}
}
RecordStore[] stores=mediator.getProductedStores();
// LoserTree lt=new LoserTree(stores);
WinnerTree lt=new WinnerTree(stores);
Record least=lt.nextLeastRecord();
ra.start();
while(!least.isNull())
{
ra.acceptRecord(least);
least=lt.nextLeastRecord();
}
ra.end();
for(int i=0;i<stores.length;i++)
{
stores[i].destroy();
}
}
public static void main(String[] args) throws IOException
{
// RecordStore store=new MemRecordStore(60004,true);
// RunAcceptor mediator=new MemRunAcceptor();
// ResultAcceptor ra=new MemResultAcceptor();
ExternalSorter sorter=new ExternalSorter();
RecordStore store=new FileRecordStore("test_sort.txt");
RunAcceptor mediator=new FileRunAcceptor("test_sort");
ResultAcceptor ra=new FileRecordStore("test_sorted.txt");
sorter.sort(70000, store, mediator, ra);
}
}
其余的都打包在此！
源碼