《数据结构基础探秘：二路归并的外部排序传奇》_程序员社区

《数据结构基础探秘：二路归并的外部排序传奇》

【番外篇：多路归并的外排史诗】目录

前言：
---------------介绍---------------
一、实际情景
二、外部排序
- 什么是外部排序？
三、多路归并排序
- 什么是多路归并排序？
---------------实现---------------
四、文件归并
- 文件二路归并排序思路是什么？
- 文件二路归并排序怎么实现？
- 头文件：ExternalSort.h
- 实现文件：ExternalSort.c
- 主程序文件：Main.c
- 运行结果

在这里插入图片描述

前言：

小伙伴们，许久不见啦！(づ｡◕‿‿◕｡)づ博主今日正式带来 《多路归并外排的番外传奇》 哟！✨
郑重声明：博主可没“消失”哦～～(￣▽￣)ゞ这篇博文其实早已就绪，特意选在端午节这个特别时刻发布～🎉
🎉不只是端午节🐲，还是咱们《数据结构初阶》系列的收官之日呢！🥳
从博主首发的《数据结构初阶》博文【时间复杂度与空间复杂度】到如今，已然悄然过了约一个半月，时光飞逝呀！😭
此文篇幅虽不算长（约4千字），却完整涵盖了理论到实践的全流程～📖
相信读完本文，你定能精通 大文件外部排序——二路归并排序* 的核心原理与实现！٩(◕‿◕｡)۶

---------------介绍---------------

一、实际场景

当需要排序的数据量远远超出计算机内存的承载能力时，直接运用常规的内部排序算法（比如：快速排序、归并排序等，之前所学的八大排序皆为内部排序）会遭遇数据无法完全载入内存的难题。
若数据无法一次性载入内存进行处理，便需借助外部存储设备（像：硬盘、U盘等），通过内存与外存之间的多次数据交互来达成排序。
因而，我们得依靠 外部排序 算法，通过协调内存与外部存储设备间的数据往来，分阶段完成排序工作。

二、外部排序

何为外部排序？

外部排序（External Sorting） ：是用于处理数据量远大于计算机内存容量的排序技术。
外部排序的核心思路：
- 将大规模数据分割成多个可处理的小数据块，先在内存里对每个数据块开展排序，生成有序归并段；
- 再借助多路归并等策略逐步合并这些有序段，最终获取完整的有序数据集。

这种方式成功突破内存容量的限制，成为处理海量数据排序的重要技术途径。

简而言之，外部排序是内存告急时的「排序神器」：它凭借「分割数据→内存排序→归并合并」的流程，解决了传统排序无法应对海量数据的弊端，本质是一种「借助外存拓展内存能力」的工程化解决方案。

因此，接下来我们来认识外部排序的经典方法：多路归并排序

三、多路归并排序

何谓多路归并排序？

多路归并排序（Multi-way Merge Sort） ：是外部排序中常用的关键技术，用于解决「数据量远大于内存容量」时的排序问题。
- 其本质是把多个有序的子序列（归并段）逐步合并成一个完整的有序序列；
- 它是传统二路归并排序的拓展，能同时合并K个有序序列，大幅减少归并的轮次。

多路归并排序的核心原理与流程：
外部排序一般分为两个阶段：预处理阶段（生成归并段）和归并阶段（合并有序段）。

1. 预处理阶段：生成初始归并段
- 步骤：
- 把大文件分割成若干小数据块，每个块的大小不超过内存容量；
- 依次将每个块读入内存，运用内部排序算法（例如：快速排序）进行排序，生成有序的归并段（临时文件）。
- 示例：若内存可容纳100MB数据，原始文件为1GB，则可分成10个100MB的块，分别排序后得到10个有序的归并段。

2. 归并阶段：合并归并段
- 核心理念：利用多路归并算法（比如：k路归并），每次从k个归并段中读取最小的数据，合并成最终的有序文件。
- 关键要点：
- 降低磁盘I/O次数：通过增加归并路数k（受内存限制），减少归并的轮次；
- 缓冲区管理：在内存中为每个归并段分配输入缓冲区和输出缓冲区，以此减少读写次数。

---------------实现---------------

四、文件归并

文件二路归并排序的思路是怎样的？

文件数据的排序与归并流程：

1. 初始分块排序
- 从原始数据里每次读取n个值，排序后分别写入两个临时文件file1和file2；
- 举例：首次读取前n个值排序后写入file1，接着读取接下来的n个值排序后写入file2。

2. 首次归并操作
- 运用归并排序的思想，同时读取file1和file2中的数据，逐段比较二者的当前最小值；
- 将较小的值依次追加到一个新文件mfile中，最终让mfile合并成一个有序文件。

3. 文件清理与重命名
- 删除已完成归并的file1和file2；
- 将mfile重新命名为file1，作为下一轮归并的基础有序文件。

4. 后续分块与归并循环
- 再次从原始数据中读取n个值，排序后写入新的file2（若原始数据已读完，则跳过此步骤）；
- 重复步骤2的归并流程：将file1（前一轮的有序结果）与file2（新排序的块）合并到mfile，然后删除旧文件并把mfile重命名为file1。

5. 终止条件与结果
- 持续上述循环，直到无法再从原始数据中读出n个值；
- 最终，所有数据经过多次归并后形成的完整有序数据会存储在file1中。

在这里插入图片描述

文件二路归并排序怎么实现？

头文件：ExternalSort.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void CreateNData();
int complete(const void* a, const void* b);

int ReadNDataSortToFile(FILE* fout, int n, const char* file1);
void MergeFile(const char* file1, const char* file2, const char* mfile);

实现文件：ExternalSort.c

#include "ExternalSort.h"

void CreateNData() {
    const int N = 10000000;
    srand((unsigned int)time(NULL));
    const char* file = "data.txt";
    FILE* fin = fopen(file, "w");
    if (fin == NULL) {
        perror("fopen fail");
        return;
    }
    for (int i = 0; i < N; i++) {
        int x = rand() + i;
        fprintf(fin, "%d\n", x);
    }
    fclose(fin);
}

int complete(const void* a, const void* b) {
    const int* pa = (const int*)a;
    const int* pb = (const int*)b;
    return (*pa - *pb);
}

int ReadNDataSortToFile(FILE* fout, int n, const char* file) {
    int* a = (int*)malloc(n * sizeof(int));
    if (a == NULL) {
        perror("malloc fail");
        return 0;
    }
    int x, num = 0;
    for (int i = 0; i < n; i++) {
        if (fscanf(fout, "%d", &x) == EOF) break;
        a[num++] = x;
    }
    if (num == 0) {
        free(a);
        return 0;
    }
    qsort(a, num, sizeof(int), complete);
    FILE* fin = fopen(file, "w");
    if (fin == NULL) {
        free(a);
        perror("fopen fail");
        return 0;
    }
    for (int i = 0; i < num; i++) {
        fprintf(fin, "%d\n", a[i]);
    }
    free(a);
    fclose(fin);
    return num;
}

void MergeFile(const char* file1, const char* file2, const char* mfile) {
    FILE* fout1 = fopen(file1, "r");
    if (fout1 == NULL) {
        perror("fopen fail for file1");
        return;
    }
    FILE* fout2 = fopen(file2, "r");
    if (fout2 == NULL) {
        perror("fopen fail for file2");
        fclose(fout1);
        return;
    }
    FILE* fin = fopen(mfile, "w");
    if (fin == NULL) {
        perror("fopen fail for mfile");
        fclose(fout1);
        fclose(fout2);
        return;
    }
    int x1, x2, ret1, ret2;
    ret1 = fscanf(fout1, "%d", &x1);
    ret2 = fscanf(fout2, "%d", &x2);
    while (ret1 != EOF && ret2 != EOF) {
        if (x1 < x2) {
            fprintf(fin, "%d\n", x1);
            ret1 = fscanf(fout1, "%d", &x1);
        } else {
            fprintf(fin, "%d\n", x2);
            ret2 = fscanf(fout2, "%d", &x2);
        }
    }
    while (ret1 != EOF) {
        fprintf(fin, "%d\n", x1);
        ret1 = fscanf(fout1, "%d", &x1);
    }
    while (ret2 != EOF) {
        fprintf(fin, "%d\n", x2);
        ret2 = fscanf(fout2, "%d", &x2);
    }
    fclose(fout1);
    fclose(fout2);
    fclose(fin);
}

主程序文件：Main.c

#include "ExternalSort.h"

int main() {
    // CreateNData();
    const char* file1 = "file1.txt";
    const char* file2 = "file2.txt";
    const char* mfile = "mfile.txt";
    FILE* fout = fopen("data.txt", "r");
    if (fout == NULL) {
        perror("fopen fail");
        return 1;
    }
    int M = 1000000;
    ReadNDataSortToFile(fout, M, file1);
    ReadNDataSortToFile(fout, M, file2);
    while (1) {
        MergeFile(file1, file2, mfile);
        if (remove(file1) != 0) perror("Warning: Failed to remove file1");
        if (remove(file2) != 0) perror("Warning: Failed to remove file2");
        if (rename(mfile, file1) != 0) {
            perror("Warning: Failed to rename mfile");
            break;
        }
        int read_count = ReadNDataSortToFile(fout, M, file2);
        if (read_count == 0) break;
        if (read_count < M) {
            printf("最后一块有 %d 个元素\n", read_count);
        }
    }
    fclose(fout);
    return 0;
}

运行结果

文件归并操作

在这里插入图片描述

文章整理自互联网，只做测试使用。发布者：Lomu，转转请注明出处：https://www.it1024doc.com/12768.html

《数据结构基础探秘：二路归并的外部排序传奇》