面试题：C语言实现外部排序算法

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

#define MAX_BUFFER_SIZE 1024
#define TEMP_FILE_PREFIX "temp_file_"

// 合并两个已排序的临时文件到输出文件
void merge_files(const char *file1, const char *file2, const char *output_file) {
    FILE *f1 = fopen(file1, "r");
    FILE *f2 = fopen(file2, "r");
    FILE *out = fopen(output_file, "w");
    int num1, num2;
    int read1 = fscanf(f1, "%d", &num1);
    int read2 = fscanf(f2, "%d", &num2);

    while (read1 != EOF && read2 != EOF) {
        if (num1 <= num2) {
            fprintf(out, "%d\n", num1);
            read1 = fscanf(f1, "%d", &num1);
        } else {
            fprintf(out, "%d\n", num2);
            read2 = fscanf(f2, "%d", &num2);
        }
    }

    while (read1 != EOF) {
        fprintf(out, "%d\n", num1);
        read1 = fscanf(f1, "%d", &num1);
    }

    while (read2 != EOF) {
        fprintf(out, "%d\n", num2);
        read2 = fscanf(f2, "%d", &num2);
    }

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

// 对内存中的数组进行排序
void sort_array(int *arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 外部排序主函数
void external_sort(const char *input_file, const char *output_file) {
    FILE *input = fopen(input_file, "r");
    if (!input) {
        perror("无法打开输入文件");
        return;
    }

    int buffer[MAX_BUFFER_SIZE];
    int file_count = 0;
    char temp_file_name[128];

    // 分块读取并排序
    while (1) {
        int count = 0;
        while (count < MAX_BUFFER_SIZE && fscanf(input, "%d", &buffer[count]) != EOF) {
            count++;
        }

        if (count == 0) break;

        sort_array(buffer, count);

        sprintf(temp_file_name, "%s%d", TEMP_FILE_PREFIX, file_count++);
        FILE *temp_file = fopen(temp_file_name, "w");
        for (int i = 0; i < count; i++) {
            fprintf(temp_file, "%d\n", buffer[i]);
        }
        fclose(temp_file);
    }

    fclose(input);

    // 合并临时文件
    while (file_count > 1) {
        for (int i = 0; i < file_count / 2; i++) {
            sprintf(temp_file_name, "%s%d", TEMP_FILE_PREFIX, i);
            char file1[128];
            char file2[128];
            sprintf(file1, "%s%d", TEMP_FILE_PREFIX, 2 * i);
            sprintf(file2, "%s%d", TEMP_FILE_PREFIX, 2 * i + 1);
            merge_files(file1, file2, temp_file_name);
            remove(file1);
            remove(file2);
        }
        if (file_count % 2 != 0) {
            sprintf(temp_file_name, "%s%d", TEMP_FILE_PREFIX, file_count - 1);
            char new_name[128];
            sprintf(new_name, "%s%d", TEMP_FILE_PREFIX, file_count / 2);
            rename(temp_file_name, new_name);
        }
        file_count = (file_count + 1) / 2;
    }

    // 重命名最后一个临时文件为输出文件
    sprintf(temp_file_name, "%s0", TEMP_FILE_PREFIX);
    rename(temp_file_name, output_file);
}

int main() {
    const char *input_file = "input.txt";
    const char *output_file = "output.txt";
    external_sort(input_file, output_file);
    return 0;
}

分块读取与排序：
- 每次从输入文件读取MAX_BUFFER_SIZE个整数到内存数组buffer中。
- 对数组buffer使用简单的冒泡排序算法进行排序（实际应用中可以用更高效的排序算法如快速排序等）。
- 将排序后的数组写入临时文件，每个临时文件命名为temp_file_0，temp_file_1等。
合并临时文件：
- 不断合并临时文件，每次合并两个已排序的临时文件，并将结果写入新的临时文件。
- 最后将合并后的文件重命名为输出文件。

这个实现假设输入文件中的整数以换行符分隔。如果实际格式不同，需要相应修改读取整数的代码部分。

面试题：C语言实现外部排序算法

知识考点

面试题答案