外排序之⽂件归并排序实现
外排序介绍
外排序（External sorting）是指能够处理极⼤量数据的排序算法。通常来说，外排序处理的数据不能
⼀次装⼊内存，只能放在读写较慢的外存储器(通常是硬盘)上。外排序通常采⽤的是⼀种“排序-归
并”的策略。在排序阶段，先读⼊能放在内存中的数据量，将其排序输出到⼀个临时⽂件，依此进
⾏，将待排序数据组织为多个有序的临时⽂件。然后在归并阶段将这些临时⽂件组合为⼀个⼤的有序
⽂件，也即排序结果。
跟外排序对应的就是内排序，我们之前讲的常⻅的排序，都是内排序，他们排序思想适应的是数据在
内存中，⽀持随机访问。归并排序的思想不需要随机访问数据，只需要依次按序列读取数据，所以归
并排序既是⼀个内排序，也是⼀个外排序。
⽂件归并排序思路分析
- 读取n个值排序后写到file1，再读取n个值排序后写到file2
- file1和file2利⽤归并排序的思想，依次读取⽐较，取⼩的尾插到mfile，mfile归并为⼀个有序⽂件
- 将file1和file2删掉，mfile重命名为file1
- 再次读取n个数据排序后写到file2
- 继续⾛file1和file2归并，重复步骤2，直到⽂件中⽆法读出数据。最后归并出的有序数据放到了
file1中
⽂件归并排序代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 选出左右孩⼦中⼤的那⼀个if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{// 建堆 -- 向下调整建堆 -- O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// O(N*logNint end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}
// file1⽂件的数据和file2⽂件的数据归并到mfile⽂件中
void MergeFile(const char* file1, const char* file2, const char* mfile)
{FILE* fout1 = fopen(file1, "r");if (fout1 == NULL){printf("打开⽂件失败\n");exit(-1);}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){printf("打开⽂件失败\n");exit(-1);}FILE* fin = fopen(mfile, "w");if (fin == NULL){printf("打开⽂件失败\n");exit(-1);}// 这⾥跟内存中数组归并的思想完全类似，只是数据在硬盘⽂件中⽽已// 依次读取file1和file2的数据，谁的数据⼩，谁就往mfile⽂件中去写// file1和file2其中⼀个⽂件结束后，再把另⼀个⽂件未结束⽂件数据，// 依次写到mfile的后⾯int num1, num2;int ret1 = fscanf(fout1, "%d\n", &num1);int ret2 = fscanf(fout2, "%d\n", &num2);while (ret1 != EOF && ret2 != EOF){if (num1 < num2){fprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);}else{fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);}}while (ret1 != EOF){fprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);}while (ret2 != EOF){fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);}fclose(fout1);fclose(fout2);fclose(fin);
}
// 返回读取到的数据个数
int ReadNNumSortToFile(FILE* fout, int* a, int n, const char* file)
{int x = 0;// 读取n个数据放到fileint i = 0;while (i < n && fscanf(fout, "%d", &x) != EOF){a[i++] = x;}// ⼀个数据都没有读到，则说明⽂件已经读到结尾了if (i == 0)return i;// 排序HeapSort(a, i);FILE* fin = fopen(file, "w");if (fout == NULL){printf("打开⽂件%s失败\n", file);exit(-1);}for (int j = 0; j < i; j++){fprintf(fin, "%d\n", a[j]);}fclose(fin);return i;
}
// MergeSortFile的第⼆个是每次取多少个数据到内存中排序，然后写到⼀个⼩⽂件进⾏归并
// 这个n给多少取决于我们有多少合理的内存可以利⽤，相对⽽⾔n越⼤，更多数据到内存中排序后，
// 再⾛⽂件归并排序，整体程序会越快⼀些。
void MergeSortFile(const char* file, int n)
{FILE* fout = fopen(file, "r");if (fout == NULL){printf("打开⽂件%s失败\n", file);exit(-1);}int i = 0;int x = 0;const char* file1 = "file1";const char* file2 = "file2";const char* mfile = "mfile";// 分割成⼀段⼀段数据，内存排序后写到，⼩⽂件，int* a = (int*)malloc(sizeof(int) * n);if (a == NULL){perror("malloc fail");return;}// 分别读取前n个数据排序后，写到file1和file2⽂件ReadNNumSortToFile(fout, a, n, file1);ReadNNumSortToFile(fout, a, n, file2);while (1){// file1和file2⽂件归并到mfile⽂件中MergeFile(file1, file2, mfile);// 删除file1和file2if (remove(file1) != 0 || remove(file2) != 0){perror("Error deleting file");return;}// 将mfile重命名为file1if (rename(mfile, file1) != 0){perror("Error renaming file");return;}// 读取N个数据到file2，继续⾛归并// 如果⼀个数据都没读到，则归并结束了if (ReadNNumSortToFile(fout, a, n, file2) == 0){break;}}printf("%s⽂件成功排序到%s\n", file, file1);fclose(fout);free(a);
}
// 创建N个随机数，写到⽂件中
void CreateNDate()
{// 造数据int n = 1000000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = rand() + i;fprintf(fin, "%d\n", x);}fclose(fin);
}
int main()
{//CreateNDate();MergeSortFile("data.txt", 100000);return 0;
}
