外部排序实现使用堆来生成若干个顺串，然后使用多路归并算法来生成最终排序好的内容。
本来打算使用败者树，结果发现败者树当参与的竞赛者相对较多的情况下，没有全部完成就被空节点充满了。
这个按照它的严格算法，其实也是可以知道不能保证总是能排完的。天快亮了，才彻底放弃使用败者树。改成实现赢者树，结果发现赢者树能保证不出错，实现竟也顺手。
最后整了个测试文件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);
}
}
其余的都打包在此！
源码