外部排序?qū)崿F(xiàn)使用堆來生成若干個(gè)順串，然后使用多路歸并算法來生成最終排序好的內(nèi)容。
本來打算使用敗者樹，結(jié)果發(fā)現(xiàn)敗者樹當(dāng)參與的競賽者相對(duì)較多的情況下，沒有全部完成就被空節(jié)點(diǎn)充滿了。
這個(gè)按照它的嚴(yán)格算法，其實(shí)也是可以知道不能保證總是能排完的。天快亮了，才徹底放棄使用敗者樹。改成實(shí)現(xiàn)贏者樹，結(jié)果發(fā)現(xiàn)贏者樹能保證不出錯(cuò)，實(shí)現(xiàn)竟也順手。
最后整了個(gè)測試文件500M的隨機(jī)內(nèi)容，2~3分鐘排序完成了（應(yīng)該還可以優(yōu)化），感覺還行。
代碼較多，最要考慮到以后可能要重用。
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);
}
}
其余的都打包在此！
源碼