多路归并排序 & 有序文件的外部排序

看以下内容之前，请确保你已经学过抖码算法课程 A [中级篇二：常用高层数据结构【老汤数据结构与算法课四】](https://ke.qq.com/course/3098167?tuin=1bf872a6) 中的 **堆和优先队列**

如果你再学习完抖码算法课程 B 中的 [刷题篇第 15 天：链表(二)](https://ke.qq.com/course/3518917?tuin=1bf872a6) 中的**lc 23：合并K个升序链表**，那么效果更好

## 多路归并排序

请看下面的代码：

```java
package com.douma.practical.mult_line_merging;

import java.util.*;

/**
 * 抖码算法，让算法学习变的简单有趣
 *
 * @作者 : 老汤
 */
public class KSortedArrayMerger {

/**
     * 多路归并排序
     * 给定 k 个升序的数组，将它们合并成一个有序的数组
     * 例如：
     *  输入： k = 3
     *      a = [1, 2, 6, 9, 10]
     *      b = [2, 3, 7, 11]
     *      c = [4, 8, 9, 13]
     *      d = [5]
     *  输出：
     *      [1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13]
     *
     *  tips：使用小顶堆实现排序
     *
     *  假设每个数组的平均长度为 n
     *  时间复杂度：O(n*k*log(k))
     *  空间复杂度：O(n*k)
     */
    public int[] mergeKSortedArray(List<int[]> data, int k) {
        // 1. 计算合并之后的数组的总长度
        int len = 0;
        for (int i = 0; i < k; i++) {
            len += data.get(i).length;
        }

// 2. 初始化结果数组
        int[] res = new int[len];

// 3. 初始化一个大小为 k 的小顶堆
        // 小顶堆中的每个节点存储 3 个值： [value, whichArray, valueIndex]
        // value 表示数组中的元素值
        // whichArray 表示 value 所属的数组
        // valueIndex 表示 value 在所属数组中的索引
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(k, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 先按照 value 排序，value 小的放在堆顶
                // value 相等的话，按照 value 所属的数组在 data 中的索引排序，如果小的放在堆顶，这个其实排不排序都无所谓
                return o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1];
            }
        });

// 4. 将 k 个数组的第一个元素值都放入到堆中
        for (int i = 0; i < k; i++) {
            if (data.get(i).length == 0) continue;
            minHeap.add(new int[]{data.get(i)[0], i, 0});
        }

// 5. 合并排序
        int index = 0;
        while (!minHeap.isEmpty()) {
            // 5.1 拿到堆顶最小的元素
            int[] record = minHeap.poll();
            int value = record[0];
            int whichArray = record[1];
            int valueIndex = record[2];

// 5.2 将最小元素放入到结果中
            res[index++] = value;

// 5.3 处理这个 value 所在的数组的下一个元素
            valueIndex++;
            // 如果没有下一个元素了，则不做任何处理
            if (valueIndex == data.get(whichArray).length) continue;
            // 将下一个元素及其位置信息放入到堆中
            minHeap.add(new int[]{data.get(whichArray)[valueIndex], whichArray, valueIndex});
        }

return res;
    }

public static void main(String[] args) {
        int[] a = {1, 2, 6, 9, 10};
        int[] b = {2, 3, 7, 11};
        int[] c = {4, 8, 9, 13};
        int[] d = {5};

List<int[]> data = new ArrayList<>();
        data.add(a);
        data.add(b);
        data.add(c);
        data.add(d);

int[] res = new KSortedArrayMerger().mergeKSortedArray(data, 4);
        System.out.println(Arrays.toString(res));
    }
}

```

## 文件外部排序

我们将上面的数组换成文件，假设输入的是若干个文件，每个文件中的每一行都是一个单词，并且每个文件中的单词都是有序的。

比如，以下是文件 1 的内容：

```
abb
bar
bbbb
cddd
```

以下是文件 2 的内存：

```
aaaa
aabb
ccdd
dddd
```

以下是文件 3 的内容：

```
bbabb
ccdh
dgj
```

最终我们需要将上面 3 个有序的文件合并成一个有序的文件：

```
aaaa
aabb
bar
bbabb
bbbb
ccdd
ccdh
cddd
dddd
dgj
```

我们先写一个 BufferedIterator 类，如下：

```java
package com.douma.practical.mult_line_merging;

import java.io.BufferedReader;
import java.io.IOException;

// BufferedIterator 是对文件输入流 BufferedReader 的包装，用于：
//  ① 判断输入流中是否还有数据，有过有的话，则先缓存下一行数据
//  ② 得到文件输入流中的下一行数据
public class BufferedIterator {

private BufferedReader reader;
    private String head;

BufferedIterator(BufferedReader reader) {
        this.reader = reader;
    }

public boolean hasNext() {
        try {
            head = this.reader.readLine();
        } catch (IOException e) {
            e.printStackTrace();
            head = null;
        }
        return head != null;
    }

public String next() {
        return head;
    }

public void close() throws Exception {
        this.reader.close();
    }
}

```

然后使用多路归并排序来实现文件的外部排序，如下代码：

```java
package com.douma.practical.mult_line_merging;

import java.io.*;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 对有序的小文件进行外部排序
 * 使用多路归并排序实现
 */
public class _3_ExternalSorter {

public void mergeSort(String dirName) throws Exception {

File dir = new File(dirName);
        File[] children = dir.listFiles();

// 1. 初始化一个最小堆，大小就是有序小文件的个数
        // 堆中的每个节点存放每个有序小文件对应的输入流
        // BufferedIterator 是对文件输入流 BufferedReader 的包装，用于：
        //  ① 判断输入流中是否还有数据
        //  ② 得到文件输入流中的下一行数据
        PriorityQueue<BufferedIterator> minHeap = new PriorityQueue<>(children.length, new Comparator<BufferedIterator>() {
            @Override
            public int compare(BufferedIterator o1, BufferedIterator o2) {
                // 按照每个有序文件中的下一行数据对所有文件输入流进行排序
                // 单词小的输入文件流放在堆顶
                return o1.next().compareTo(o2.next());
            }
        });

// 2. 将所有有序文件的输入流包装成 BufferedIterator 放入到堆中
        for (File file : children) {
            BufferedReader br = FileIOUtils.getReader(file.getName());
            BufferedIterator buf = new BufferedIterator(br);
            // 要有数据才放入到堆中，否则关闭流
            if (buf.hasNext()) {
                minHeap.add(buf);
            } else {
                buf.close();
            }
        }

BufferedWriter bw = FileIOUtils.getWriter("data\\top100\\sorted_words.txt");
        // 3. 拿出堆顶的数据，并写入到最终排序的文件中
        while (!minHeap.isEmpty()) {
            BufferedIterator firstBuf = minHeap.poll();
            bw.write(firstBuf.next());
            bw.newLine();
            // 如果拿出来的输入流中还有数据的话，那么将这个输入流再一次添加到栈中，
            if (firstBuf.hasNext()) {
                minHeap.add(firstBuf);
            } else { // 否则说明该文件输入流中没有数据了，那么可以关闭这个流
                firstBuf.close();
            }
        }

FileIOUtils.closeWriter(bw);
    }

public static void main(String[] args) throws Exception {
        String dirName = "data\\top100\\sorted_data\\";
        new _3_ExternalSorter().mergeSort(dirName);
    }

}

```

看完上面的内容后，请思考这个问题：[学员提供的算法面试题 - 06 【单词频率 top 100】](https://gitee.com/douma_edu/douma_algo_training_camp/issues/I4VWZR)

上面代码用到的文件 IO 的工具类如下：

```java
package com.douma.practical.mult_line_merging;

import java.io.*;

/**
 * 抖码算法，让算法学习变的简单有趣
 *
 * @作者 : 老汤
 */
public class FileIOUtils {

// 拿到指定文件的输入流，并包装成文件 BufferedReader
    public static BufferedReader getReader(String name) {
        try {
            FileInputStream inputStream = new FileInputStream(name);
            BufferedReader br = new BufferedReader(new InputStreamReader(inputStream));
            return br;
        } catch (IOException e) {
            throw new RuntimeException("IOException", e);
        }
    }

// 拿到指定文件的输出流，并包装成文件 BufferedWriter
    public static BufferedWriter getWriter(String name) {
        try {
            FileOutputStream outputStream = new FileOutputStream(name);
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(outputStream));
            return bw;
        } catch (IOException e) {
            throw new RuntimeException("IOException", e);
        }
    }

public static void closeReader(Reader reader) {
        try {
            if (reader != null) {
                reader.close();
            }
        } catch (IOException e) {
            throw new RuntimeException("IOException", e);
        }
    }

public static void closeWriter(Writer writer) {
        try {
            if (writer != null) {
                writer.close();
            }
        } catch (IOException e) {
            throw new RuntimeException("IOException", e);
        }
    }
}

```

老汤/douma-algo

内容风险标识

评论 (1)

老汤/douma-algo .gitee-modal { width: 500px !important; }

内容风险标识