外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。选自百度百科。
第一步: 首先我们先来创建一个大号的文件。
public class Sort {
public static void main(String[] args) throws IOException{
File file=new File("E:/排序/source.txt");
int numCount=10000000;
Random r=new Random();
if(file.exists())file.delete();
FileWriter fw=new FileWriter(file);
for(int i=0;i<numCount;i++){
fw.write(r.nextInt()+"\n");
}
fw.close();
}
文件不是很大,也就107M左右,当然我们可以修改numCount来让这个文件变得更大。
第二步,外部排序,以下是完整代码
package sort;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class Sort {
public static void main(String[] args) throws IOException{
File file=new File("E:/排序/source.txt");
BufferedReader fr=new BufferedReader(new FileReader(file));//源数据文件读取。
final int SIZE=10000;//这里是定义我们将源文件中以10000条记录作为单位进行分割。
int[] nums=new int[SIZE];//临时存放分割时的记录
List<String> fileNames=new ArrayList<String>();//保存所有分割文件的名称
int index=0;
while(true){
String num=fr.readLine();//从原文件中读取一条记录
if(num==null){//如果读取完毕后,进行一次排序并保存
fileNames.add(sortAndSave(nums,index));
break;
}
nums[index]=Integer.valueOf(num);
index++;
if(index==SIZE){//当nums里面读的数字到达长度边界时,排序,存储
fileNames.add(sortAndSave(nums,index));//sortAndSave是将nums中前index条记录先快速排序,然后存入文件,最好将文件名返回。
index=0;//重置index
}
}
fr.close();
mergeSort(fileNames);//将所有fileNames的文件进行合并
}
//sortAndSave是将nums中前index条记录先快速排序,然后存入文件,最好将文件名返回
public static String sortAndSave(int[] nums,int size) throws IOException{
quicksort.sort(nums,0, size-1);
String fileName="E:/排序/sort"+System.nanoTime()+".txt";
File rf=new File(fileName);
BufferedWriter bw=new BufferedWriter(new FileWriter(rf));
for(int i=0;i<nums.length;i++)bw.write(nums[i]+ "\n");
bw.close();
return fileName;
}
public static void mergeSort(List<String> fileNames) throws IOException{
List<String> tempFileNames=new ArrayList<String>();
for(int i=0;i<fileNames.size();i++){
String resultFileName="E:/排序/sort"+System.nanoTime()+".txt";
File resultFile=new File(resultFileName);
tempFileNames.add(resultFileName);
BufferedWriter bw=new BufferedWriter(new FileWriter(resultFile));
File file1=new File(fileNames.get(i++));
BufferedReader br1=new BufferedReader(new FileReader(file1));
if(i<fileNames.size()){
File file2=new File(fileNames.get(i));
BufferedReader br2=new BufferedReader(new FileReader(file2));
int num1=0;
int num2=0;
boolean isFirst=true;
boolean firstNext=true;
String numVal1=null,numVal2=null;
for(;;){
if(isFirst){
numVal1=br1.readLine();
numVal2=br2.readLine();
num1=Integer.valueOf(numVal1);
num2=Integer.valueOf(numVal2);
isFirst=false;
}
else if(firstNext)
numVal1=br1.readLine();
else
numVal2=br2.readLine();
if(numVal1!=null && numVal2!=null){
if(firstNext){
num1=Integer.valueOf(numVal1);
}else{
num2=Integer.valueOf(numVal2);
}
if(num1<num2){
bw.write(num1+"\n");
firstNext=true;
}else{
bw.write(num2+"\n");
firstNext=false;
}
}else{
if(numVal1!=null)bw.write(numVal1+"\n");
if(numVal2!=null)bw.write(numVal2+"\n");
break;
}
}
while(true){
numVal2=br2.readLine();;
if(numVal2!=null)bw.write(numVal2+"\n");
else break;
}
br2.close();
file2.delete();
}
while(true){
String numVal1=br1.readLine();
if(numVal1!=null){
bw.write(numVal1+"\n");
}
else break;
}
br1.close();
file1.delete();
bw.close();
}
int size=tempFileNames.size();
if(size>1){
mergeSort(tempFileNames);
}else if(size==1){
File file=new File(tempFileNames.get(0));
file.renameTo(new File("E:/排序/result.txt"));
}
}}
//快速排序
class quicksort {
public static void sort(int data[],int low,int hight){
quicksort qs=new quicksort();
qs.data=data;
qs.sort(low, hight);
}
public int data[];
private int partition(int sortArray[], int low, int hight) {
int key = sortArray[low];
while (low < hight) {
while (low < hight && sortArray[hight] >= key)hight--;
sortArray[low] = sortArray[hight];
while (low < hight && sortArray[low] <= key)low++;
sortArray[hight] = sortArray[low];
}
sortArray[low] = key;
return low;
}
public void sort(int low, int hight) {
if (low < hight) {
int result = partition(data, low, hight);
sort(low, result - 1);
sort(result + 1, hight);
}
}
public void display() {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i]);
System.out.print(" ");
}
}
}
分享到:
相关推荐
用java实现基于整数(int)的外部排序
有文件大小为1G的一个文件,文件每行存储的为URL及其访问次数,例如/api/auth/login 2 ,计算出访问次数最多的前5个URL和其访问次数,每行的URL可能重复,计算内存限制10M。 === 内含解题思路、测试结果截图、可运行...
NULL 博文链接:https://yeelor.iteye.com/blog/1964843
利用python,JavaScript,java,go,PHP等实现: 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 堆排序 计数排序 桶排序 基数排序
NULL 博文链接:https://royzhou1985.iteye.com/blog/775550
本项目主要使用Java实现各种经典常用数据结构及其算法,包括但不仅限于链表、栈,队列,树,图等经典数据结构。 八大排序算法及其实现,具体包括直接插入排序,希尔排序,直接选择排序,堆排序,冒泡排序,快速排序...
主要介绍了Java List集合排序实现方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
SortDemo.java 排序示例 travelTwoDime.java 遍历二维数组 traversing.java 遍历一维数组 useStrBuf.java 使用StringBuffer示例 useString.java 使用String示例 YanghuiTri.java 构造和显示杨辉三角 第6章 ...
jSIP这个Java包目标是用Java实现SIP(SIP:Session Initiation Protocol)协议及SIP协议的其它扩展部 分。 Java表达式语法解析库 parboiled parboiled 是一个纯Java库提供了一种轻量级,易于使用,功能强大和优雅的PEG...
百度云盘分享 ... Java实现的FTP连接与数据浏览程序,实现实例化可操作的窗口。 部分源代码摘录: ftpClient = new FtpClient(); //实例化FtpClient对象 String serverAddr=jtfServer.getText();...
Java实现的FTP连接与数据浏览程序,实现实例化可操作的窗口。 部分源代码摘录: ftpClient = new FtpClient(); //实例化FtpClient对象 String serverAddr=jtfServer.getText(); //得到服务器地址 ...
个人实现的最小权重的二叉堆实现,效率很高,适合任意场合下的临时列表排序。 可在外部写脚本对该文件进行测试 需要继承Tuple类实现排序对象类型,并实现Tuple的抽象方法weight()来反映排序对象权重
jSIP这个Java包目标是用Java实现SIP(SIP:Session Initiation Protocol)协议及SIP协议的其它扩展部 分。 Java表达式语法解析库 parboiled parboiled 是一个纯Java库提供了一种轻量级,易于使用,功能强大和优雅的PEG...
文件_处理通过改进的快速排序进行外部排序您将为二进制数据实现外部排序算法。 输入数据文件将由许多 4 字节记录组成,每个记录由 1 到 30,000 范围内的两个 2 字节(短)整数值组成。 第一个 2 字节字段是键值...
知道实现比较器(Comparable,Comparator)用于排序算法(多态性)。 [*]了解同步包装和不可修改包装。 第12章 IO与串行化 2课时 了解Java IO 中类的层次结构,介绍Java IO采用的装饰...
jSIP这个Java包目标是用Java实现SIP(SIP:Session Initiation Protocol)协议及SIP协议的其它扩展部 分。 Java表达式语法解析库 parboiled parboiled 是一个纯Java库提供了一种轻量级,易于使用,功能强大和优雅的PEG...
jSIP这个Java包目标是用Java实现SIP(SIP:Session Initiation Protocol)协议及SIP协议的其它扩展部 分。 Java表达式语法解析库 parboiled parboiled 是一个纯Java库提供了一种轻量级,易于使用,功能强大和优雅的PEG...
jSIP这个Java包目标是用Java实现SIP(SIP:Session Initiation Protocol)协议及SIP协议的其它扩展部 分。 Java表达式语法解析库 parboiled parboiled 是一个纯Java库提供了一种轻量级,易于使用,功能强大和优雅的PEG...
jSIP这个Java包目标是用Java实现SIP(SIP:Session Initiation Protocol)协议及SIP协议的其它扩展部 分。 Java表达式语法解析库 parboiled parboiled 是一个纯Java库提供了一种轻量级,易于使用,功能强大和优雅的PEG...
jSIP这个Java包目标是用Java实现SIP(SIP:Session Initiation Protocol)协议及SIP协议的其它扩展部 分。 Java表达式语法解析库 parboiled parboiled 是一个纯Java库提供了一种轻量级,易于使用,功能强大和优雅的PEG...