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

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

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<File> files = split(file); // 分割成小文件并加载到内存排序
        multMerge(files); //归并

    }

    /**
     * Splits the original file into a number of sub files.
     */
    public List<File> split(File file) throws IOException {
        List<File> 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<File> files) throws IOException {
        //构建输出缓冲流
        BufferedWriter out = new BufferedWriter(new FileWriter(OUT_FILE), BUFFER_SIZE);
        //构建输入缓冲流
        List<BufferedReader> 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;
    }
}

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