외부 병합 정렬 자바 구현

 

package mergesort;

import java.text.DecimalFormat;
import java.util.Random;

public class Record {
	private int A;
	private String B;
	private String C;
	
	@Override
	public String toString() {
		String tempA = new  DecimalFormat("0000000000").format(this.A);
		return tempA+"#"+B+"#"+C;
	}
	
	public String getRecordString(){
		String A = new  DecimalFormat("0000000000").format(Math.abs( new Random().nextInt()));
		String B = "  "+A;
		String C = "1111111111000000000011111111110000000000111111111100000000001111111111";
		return A+"#"+B+"#"+C;
	}
	

	public Record() {
		super();
	}

	public Record(String line) {
		super();
		String [] t = line.split("#");
		this.A = Integer.valueOf(t[0]);
		this.B = t[1];
		this.C = t[2];
	}


	public int getA() {
		return A;
	}


	public void setA(int a) {
		A = a;
	}


	public String getB() {
		return B;
	}


	public void setB(String b) {
		B = b;
	}


	public String getC() {
		return C;
	}


	public void setC(String c) {
		C = c;
	}
	
}

 
 
 

package mergesort;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Date;

/**
 *       10,000,000        ，       100     。            A，  A     。
 *    block    ，  non-spanned  ，               。Block               ，xp   4096 bytes。
 *      50M         merge-sort。
 * 
 * @author GT 2012-10-16
 *
 */
public class MergeSort {
	private int size = 10000000;//    10000000
	private int sizePerBlock = 40;//       block   4KB,       100B,    block      40
	private int sizePerMemory = 500000;//  50M        ,      100B，        50W   ,      500000
	private int fileSize = size/sizePerMemory;//            20
	private int blockSize = (size%sizePerBlock)==0?(size/sizePerBlock):(size/sizePerBlock)+1; //    250000
	private int blockSizePerFile = (sizePerMemory%sizePerBlock)==0?(sizePerMemory/sizePerBlock):(sizePerMemory/sizePerBlock)+1; //         12500
	private int charBufferSizeOfReader = 4096; //                 block      
	private int charBufferSizeOfWriter = 41943040; //                  40M
	private String fileDirectory = "F:\\record3\\";
	private String recordFile = fileDirectory+"record.txt";
	
	
	private String sortedRecordFile = fileDirectory+"sorted_record.txt";
	
	public void creat() throws Exception{
		long start = new Date().getTime();
		BufferedWriter out = new BufferedWriter(new FileWriter(recordFile));
		for(int j = 0;j<blockSize;j++){
			for(int i =0;i<sizePerBlock;i++){
				out.write(new Record().getRecordString());
				out.newLine();
			}
			out.write(new char[94]);//  94 byte
			out.newLine();//   byte
		}
	
		out.close();
		long end = new Date().getTime();
		System.out.println("       :"+(end - start)+"ms");
		
	}
	
	public void read() throws Exception{
		BufferedReader in = new BufferedReader( new FileReader(recordFile));
		String line;
		
		for(int j = 0;j<blockSize;j++){
			for(int i =0;i<sizePerBlock;i++){
				line = in.readLine();
				Record r = new Record(line);
				System.out.println(r.getB());
			}
			in.readLine();
		}
		in.close();
		
	}
	
	Comparator<Record> comparator = new Comparator<Record>(){
		public int compare(Record r1,Record r2)
		{
			if(r1.getA()>=r2.getA()) return 1;
			else return 0;
		}
	};

	public void memorySort() throws Exception{
		long start = new Date().getTime();
		BufferedReader in = new BufferedReader( new FileReader(recordFile));
		
		String line;
		for(int k =0;k<fileSize;k++){//20
			Record records[] =  new Record[sizePerMemory];
			BufferedWriter out = new BufferedWriter(new FileWriter(fileDirectory+"record_"+k+".txt"));
			for(int j = 0;j<blockSizePerFile;j++){//12500
				for(int i =0;i<sizePerBlock;i++){//40
					line = in.readLine();
					records[j*sizePerBlock+i] =new Record(line);
				}
				in.readLine();
			}
			Arrays.sort(records,comparator);//    
			
			for(int j = 0;j<blockSizePerFile;j++){//12500
				for(int i =0;i<sizePerBlock;i++){//40
					out.write(records[j*sizePerBlock+i].toString());
					out.newLine();
				}
				out.write(new char[94]);//  94 byte
				out.newLine();//   byte
			}
			out.close();
		}
		in.close();
		long end = new Date().getTime();
		System.out.println("       :"+(end - start)+"ms");
	}
	
	public void mergeSort() throws Exception{
		long start = new Date().getTime();
		BufferedWriter out = new BufferedWriter(new FileWriter(sortedRecordFile),charBufferSizeOfWriter);
		BufferedReader in [] = new BufferedReader[fileSize];
		for(int i =0;i<fileSize;i++){
			in[i] = new BufferedReader( new FileReader(fileDirectory+"record_"+i+".txt"),charBufferSizeOfReader);
		}
		Record rs[] = new Record[fileSize];
		Boolean finish [] = new Boolean[fileSize];
		for(int i =0;i<fileSize;i++) {
			rs[i]=new Record(in[i].readLine());
			finish[i]= false;
		}
		Record min;
		String line;
		int finishCount = 0;
		int count = 0;
		while(true){
			
			int firstFalse = 0;//               
			for(int i=0;i<fileSize;i++){
				if(finish[i]==true)
					firstFalse =i+1;
				else
					break;
			}
			if(firstFalse>=fileSize) break;
			if(finishCount>=fileSize) break;
			min = rs[firstFalse];
			int j =firstFalse;
			
			for(int i =firstFalse+1;i<fileSize;i++){
				if(!finish[i]&&(rs[i].getA()<min.getA())){
					min = rs[i];
					j = i;
				}
			}
			if((count!=0)&&(count%sizePerBlock==0)){
				out.write(new char[94]);//  94 byte
				out.newLine();//   byte
			}
			out.write(min.toString());
			out.newLine();
			
			
			if(!finish[j]){
				line = in[j].readLine();
				if(line!=null){
					if("".equals(line.trim()))
					{
						line = in[j].readLine();
						if(line==null){
							finish[j] = true;
							finishCount++;
						}
					}else {
						rs[j]= new Record(line);
					}
				}else {
					finish[j] = true;
					finishCount++;
				}
			}
			count++;
		}
		
		for(int i =0;i<fileSize;i++){
			in[i].close();
		}
		out.close();
		
		long end = new Date().getTime();
		System.out.println("       :"+(end - start)+"ms");	
	}
	
	public static void main(String [] args) throws Exception{

//		long start = new Date().getTime();
		MergeSort ms = new MergeSort();
//		ms.creat();
//		ms.read();
//		ms.memorySort();
		ms.mergeSort();
		
//		long end = new Date().getTime();
//		System.out.println("the time is :"+(end - start)+"ms");

	}
}