如何实现基于多路归并的外排序
本篇内容主要讲解“如何实现基于多路归并的外排序”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“如何实现基于多路归并的外排序”吧!
成都创新互联公司专注于企业成都全网营销、网站重做改版、秀洲网站定制设计、自适应品牌网站建设、HTML5、购物商城网站建设、集团公司官网建设、成都外贸网站建设公司、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为秀洲等各大城市提供网站开发制作服务。
import com.google.common.collect.Lists;
import java.io.*;
import java.util.*;
/**
* 对远远大于内存的数据进行外排序，先将文件分割为内存可以单独处理多个小文件，
* 在内存中对这些小文件进行排序，然后多路归并将这些文件合并成最终的有序大文件
*
*/
public class ExternalSort {
public static int BUFFER_SIZE = 1024 * 4 * 1000; // 一次缓冲读取
public static int LITTLE_FILE_SIZE = 10; // 每个文件的记录数
public static File IN_FILE = new File("data/f1.txt");//要排序的文件
public static File OUT_FILE = new File("data/concat");//输出合并后的有序的文件
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
//排序
long start = System.currentTimeMillis();
new ExternalSort().mSort(IN_FILE);
long end = System.currentTimeMillis();
System.out.println((end - start) / 1000 + "s");
}
/**
* 多路归并
*
* @param file
* @throws IOException
*/
public void mSort(File file) throws IOException {
List files = split(file); // 分割成小文件并加载到内存排序
multMerge(files); //归并
}
/**
* Splits the original file into a number of sub files.
*/
public List split(File file) throws IOException {
List files = Lists.newArrayList();
BufferedReader din = new BufferedReader(new FileReader(file), BUFFER_SIZE);
int[] buffer = new int[LITTLE_FILE_SIZE];
boolean fileCompleted = false;
while (!fileCompleted) {
int len = buffer.length;
for (int i = 0; i < buffer.length && !fileCompleted; i++) {
try {
buffer[i] = Integer.parseInt(din.readLine());
} catch (NumberFormatException | IOException e) {
fileCompleted = true;
len = i;
}
}
//将buffer数据排序写入文件
if (len > 0) {
Arrays.sort(buffer, 0, len);
File f = new File("data/set" + new Random().nextInt());
BufferedWriter dout = new BufferedWriter(new FileWriter(f));
for (int i = 0; i < len; i++) {
dout.write(buffer[i]+"\n");
}
dout.close();
files.add(f);
}
}
din.close();
return files;
}
/**
* 多路归并
*
* @param files
* @throws IOException
*/
public static void multMerge(List files) throws IOException {
//构建输出缓冲流
BufferedWriter out = new BufferedWriter(new FileWriter(OUT_FILE), BUFFER_SIZE);
//构建输入缓冲流
List inList = Lists.newArrayList();
int size = files.size();
for (int i = 0; i < size; i++) {
inList.add(i,new BufferedReader(new FileReader(files.get(i)), BUFFER_SIZE));
}
//构建一个数组，存放从每个输入流里取出来的数据
int[] ext = new int[size];
int left = size; //定义剩余文件数
for (int i = 0; i < size; i++) {
try {
ext[i] = Integer.parseInt(inList.get(i).readLine());
} catch (Exception e) {
ext[i] = -1;
left--;
inList.get(i).close();
}
}
//将ext数组中最小值写入文件
while (left > 0) {
int ind = getMinIndex(ext);
out.write(ext[ind]+"\n");
//然后从相应的输入流中取出下一个数据
try {
ext[ind] = Integer.parseInt(inList.get(ind).readLine());
} catch (Exception e) {
ext[ind] = -1;
left--;
inList.get(ind).close();
}
}
out.close();
}
//找到数据中最小的一个
public static int getMinIndex(int[] ext) {
//找到第一个不为-1的元素
int min;
int inx = 0;
while (true) {
if (ext[inx] != -1) {
min=ext[inx];
break;
} else {
inx++;
}
}
for (int i = 1; i < ext.length; i++) {
if (ext[i] < min && ext[i] != -1) {
min = ext[i];
inx = i;
}
}
return inx;
}
} 到此，相信大家对“如何实现基于多路归并的外排序”有了更深的了解，不妨来实际操作一番吧！这里是创新互联网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
网站标题：如何实现基于多路归并的外排序
网页网址：http://cdiso.cn/article/ijsjsp.html
