对外存数据文件的二路归并排序 C语言代码

以下是一个简单的对外存数据文件进行二路归并排序的 C 语言代码：

#include <stdio.h>
#include <stdlib.h>

#define BLOCK_SIZE 1000

void merge(FILE *f1, FILE *f2, FILE *out) {
    int x, y;
    fread(&x, sizeof(int), 1, f1);
    fread(&y, sizeof(int), 1, f2);
    while (!feof(f1) && !feof(f2)) {
        if (x < y) {
            fwrite(&x, sizeof(int), 1, out);
            fread(&x, sizeof(int), 1, f1);
        } else {
            fwrite(&y, sizeof(int), 1, out);
            fread(&y, sizeof(int), 1, f2);
        }
    }
    while (!feof(f1)) {
        fwrite(&x, sizeof(int), 1, out);
        fread(&x, sizeof(int), 1, f1);
    }
    while (!feof(f2)) {
        fwrite(&y, sizeof(int), 1, out);
        fread(&y, sizeof(int), 1, f2);
    }
}

void merge_sort(char *filename) {
    FILE *f = fopen(filename, "rb+");
    if (!f) {
        perror("Cannot open input file");
        exit(1);
    }

    fseek(f, 0, SEEK_END);
    long size = ftell(f);
    fseek(f, 0, SEEK_SET);

    long block_size = BLOCK_SIZE * sizeof(int);
    int *data = malloc(block_size);
    if (!data) {
        perror("Cannot allocate memory");
        fclose(f);
        exit(1);
    }

    for (long i = 0; i < size; i += 2 * block_size) {
        fseek(f, i, SEEK_SET);
        long left = fread(data, sizeof(int), BLOCK_SIZE, f);
        long right = fread(data + left, sizeof(int), BLOCK_SIZE, f);
        long total = left + right;

        // 内部排序
        for (int j = 0; j < total - 1; j++) {
            for (int k = j + 1; k < total; k++) {
                if (data[j] > data[k]) {
                    int temp = data[j];
                    data[j] = data[k];
                    data[k] = temp;
                }
            }
        }

        fseek(f, i, SEEK_SET);
        fwrite(data, sizeof(int), total, f);
    }

    free(data);

    while (block_size < size) {
        FILE *f1 = fopen(filename, "rb+");
        FILE *f2 = fopen(filename, "rb+");
        FILE *out = fopen("temp", "wb+");
        if (!f1 || !f2 || !out) {
            perror("Cannot open input/output file");
            fclose(f);
            exit(1);
        }

        fseek(f1, 0, SEEK_SET);
        fseek(f2, block_size, SEEK_SET);

        for (long i = 0; i + 2 * block_size < size; i += 2 * block_size) {
            fread(data, sizeof(int), BLOCK_SIZE, f1);
            for (int j = 0; j < BLOCK_SIZE && !feof(f1); j++) {
                fwrite(data + j, sizeof(int), 1, out);
            }

            fread(data, sizeof(int), BLOCK_SIZE, f2);
            for (int j = 0; j < BLOCK_SIZE && !feof(f2); j++) {
                fwrite(data + j, sizeof(int), 1, out);
            }
        }

        // 处理剩余部分
        while (!feof(f1) && !feof(f2)) {
            merge(f1, f2, out);
        }

        while (!feof(f1)) {
            int x;
            fread(&x, sizeof(int), 1, f1);
            fwrite(&x, sizeof(int), 1, out);
        }

        while (!feof(f2)) {
            int x;
            fread(&x, sizeof(int), 1, f2);
            fwrite(&x, sizeof(int), 1, out);
        }

        fclose(f1);
        fclose(f2);
        fclose(out);

        // 将结果复制回原文件
        out = fopen("temp", "rb");
        if (!out) {
            perror("Cannot open output file");
            fclose(f);
            exit(1);
        }

        fread(data, sizeof(int), BLOCK_SIZE, out);
        long i = 0;
        while (!feof(out)) {
            fseek(f, i, SEEK_SET);
            fwrite(data, sizeof(int), BLOCK_SIZE, f);
            i += BLOCK_SIZE * sizeof(int);
            fread(data, sizeof(int), BLOCK_SIZE, out);
        }

        fclose(out);
        block_size *= 2;
    }

    fclose(f);
    remove("temp");
}

int main() {
    char filename[] = "data.bin";
    merge_sort(filename);
    return 0;
}

该代码首先读取整个文件的大小，然后按照 BLOCK_SIZE 将文件划分为多个块，并对每个块进行内部排序。然后，它使用二路归并将这些块逐渐合并为更大的块，直到整个文件排序完毕。在排序过程中，程序使用了一个临时文件来存储每个块的合并结果。请注意，由于在排序过程中需要频繁地读写文件，因此程序可能会比较慢。如果需要更快的排序算法，可以考虑使用其他排序算法，例如快速排序、堆排序等。