如何实现基于多路归并的外排序

本篇内容主要讲解"如何实现基于多路归并的外排序"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"如何实现基于多路归并的外排序"吧!

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;    }}

到此，相信大家对"如何实现基于多路归并的外排序"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！