归并排序分析：归并排序处理的数据量一般很大，无法直接在内存中排序。首先将要排序的文件分为几个大小可以加载到内存空间的小文件，再使用内部排序法将各个小文件内的数据排序，接着将第一步所建立的小文件每两个合并成一个大文件，两两合并后，把所有文件合并成一个文件后就可以完成排序了。
假设我们有一个原数据文件datafile.txt,我们现在需要先把它分成两个子数据文件sort1.txt和sort2.txt，然后分别用内部排序法比如冒泡排序将两个子数据文件中的数据元素排序完毕，接下来就要将排序完毕的子数据文件合并为一个新的数据文件sortdata.txt，结束操作。（注意：这里的数据文件每进行一次输出流写入操作，原数据文件中存在的元素将被覆盖为新的排序完毕的元素）
详细参考如下代码及注释，很快容易理解：
import java.io.*;
public class MergeSortBook {
public static void showData(File p)throws Exception {//打印文件中元素出来
char str;
int str1;
BufferedReader pfile=new BufferedReader(new FileReader(p));
while(true) {
str1=pfile.read();
str=(char)str1;
if(str1==-1)
break;
System.out.print("["+str+"]");
}
System.out.print("\n");
}
public static void me(File p,File p1,File p2,File pa)throws Exception {
char str1,str2;//str1写入sort1.txt，str2写入sort2.txt
int n1=0,n2,n;//n1统计datafile。txt中元素数目，n2记录从datafile。txt读取到的前半部分元素，n记录从datafile。txt读取到的后半部分元素
BufferedReader pfile3=new BufferedReader(new FileReader(p));//获取datafile。txt输入流
BufferedWriter pfile1=new BufferedWriter(new FileWriter(p1));//获取sort1.txt输出流
BufferedWriter pfile2=new BufferedWriter(new FileWriter(p2));//获取sort2.txt输出流
BufferedWriter pfilea=new BufferedWriter(new FileWriter(pa));//获取sortdata。txt输出流
while(true) {//第一次打开原数据文件datafile.txt的输入流pfile3，用n1统计原数据文件datafile.txt有多少个元素
n2=pfile3.read();
if(n2==-1)
break;
n1++;
}
pfile3.close();//第一次原数据文件datafile.txt的输入流pfile3关闭
BufferedReader pfile=new BufferedReader(new FileReader(p));//第二次原数据文件datafile.txt的输入流pfile打开
for(n2=0;n2<(n1/2);n2++) {//,将前半部分数据元素输出到sort1.txt文件中，n2记录了sort1.txt文件元素数目
str1=(char)pfile.read();
pfile1.write(str1);
}
pfile1.close();//sort1.txt的输出流关闭
bubble(p1,n2);//sort1.txt中使用冒泡排序
while(true) {//继续用pfile输入流读取datafile。txt文件的后半部分元素，用sort2.txt的输出流写入到sort2.txt文件中
n=pfile.read();
str2=(char)n;
if(n==-1)
break;
pfile2.write(str2);
}
pfile2.close();//sort2.txt输出流关闭
bubble(p2,n1-n2);//sort2.txt中使用冒泡排序
pfilea.close();//sortdata。txt输出流关闭
mergeSort(pa,p1,p2);//合并sort1.txt，sort2.txt为sortdata.txt
pfile.close();//datafile。txt输入流关闭
}
public static void bubble(File p1,int size)throws Exception {
char str1;
int data[]=new int[100];//将文件中的元素暂时保存到数组中，然后排序，接着将数组中的元素写入数据文件中
int i,j,tmp,flag,ii;
BufferedReader pfile=new BufferedReader(new FileReader(p1));
for(i=0;i<size;i++) {
ii=pfile.read();
if(ii==-1)
break;
data[i]=ii;
}
pfile.close();
BufferedWriter pfile1=new BufferedWriter(new FileWriter(p1));
for(i=size;i>0;i--) {
flag=0;
for(j=0;j<i;j++) {
if(data[j+1]<data[j]) {
tmp=data[j];
data[j]=data[j+1];
data[j+1]=tmp;
flag++;
}
}
if(flag==0)
break;
}
for(i=1;i<=size;i++) {
str1=(char)data[i];
pfile1.write(str1);
}
pfile1.close();
}
public static void mergeSort(File p,File p1,File p2)throws Exception {//将两个数据文件合并成一个数据文件
char str1,str2;
int n1,n2;
BufferedWriter pfile=new BufferedWriter(new FileWriter(p));
BufferedReader pfile1=new BufferedReader(new FileReader(p1));
BufferedReader pfile2=new BufferedReader(new FileReader(p2));
n1=pfile1.read();
n2=pfile2.read();
while(n1!=-1&&n2!=-1) {//分别比较两个文件输入流读取出来的元素，谁小就将小数往合并后的文件中写入，然后小数一方的输入流继续读取元素，直到有一方输入流读完数据就停止
if(n1<=n2) {
str1=(char)n1;
pfile.write(str1);
n1=pfile1.read();
}else {
str2=(char)n2;
pfile.write(str2);
n2=pfile2.read();
}
}
if(n2!=-1) {//假设是第一个文件的输入流先读取元素完毕，那么第二个输入流继续读取第二个文件中的元素到合并文件里面，直到第二个输入流也读取元素完毕
while(true) {
if(n2==-1)
break;
str2=(char)n2;
pfile.write(str2);
n2=pfile2.read();
}
}else if(n1!=-1) {//假设是第二个文件的输入流先读取元素完毕，那么第一个输入流继续读取第一个文件中的元素到合并文件里面，直到第二个输入流也读取元素完毕
while(true) {
if(n1==-1)
break;
str1=(char)n1;
pfile.write(str1);
n1=pfile1.read();
}
}
pfile.close();
pfile1.close();
pfile2.close();
}
public static void main(String[] args) throws Exception {
String filep="C:/Text/datafile.txt";// TODO Auto-generated method stub
String filep1="C:/Text/sort1.txt";//指定数据文件路径，记得提前在C盘下创建好文件
String filep2="C:/Text/sort2.txt";
String filepa="C:/Text/sortdata.txt";
File fp=new File(filep);//声明文件指针
File fp1=new File(filep1);
File fp2=new File(filep2);
File fpa=new File(filepa);
if(!fp.exists()) {//文件开启成功返回FILE文件，失败返回NULL值
System.out.print("开启数据文件失败\n");
}else if(!fp1.exists()) {
System.out.print("开启分割文件 1 失败\n");
}else if(!fp2.exists()) {
System.out.print("开启分割文件 2 失败\n");
}else if(!fpa.exists()) {
System.out.print("开启合并文件失败\n");
}else {
System.out.print("文件分割中......\n");
me(fp,fp1,fp2,fpa);
System.out.print("数据排序中......");
System.out.print("数据处理完成！！\n");
}
System.out.print("原始文件datafile.txt数据内容为：\n");
showData(fp);
System.out.print("\n分割文件sort1.txt数据内容为：\n");
showData(fp1);
System.out.print("\n分割文件sort2.txt数据内容为：\n");
showData(fp2);
System.out.print("\n分割文件sortdata.txt数据内容为：\n");
showData(fpa);
}
}
执行结果：
文件分割中......
数据排序中......数据处理完成！！
原始文件datafile.txt数据内容为：
[d][j][e][l][s][o][r][k][f][m][d][e][w][o][a][e][p][r][m][c]
分割文件sort1.txt数据内容为：
[d][e][f][j][k][l][m][o][r][s]
分割文件sort2.txt数据内容为：
[a][c][d][e][e][m][o][p][r][w]
分割文件sortdata.txt数据内容为：
[a][c][d][d][e][e][e][f][j][k][l][m][m][o][o][p][r][r][s][w]
网友评论