我们这里的外部排序就是利用归并排序来实现简单的数据排序
置于为什么需要外部排序，是因为在面对大量的数据的时候，我们的内存的存储空间往往不够用，这时，我们需要借助我们的外部的磁盘存储来实现我们大规模的数据排序。
#include#include #include #include //定义我们的交换函数 void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } //定义我们获取中间值的函数 int GetMidIndex(int* a, int begin, int end) { int mid = (begin + end) / 2; if (a[begin] < a[mid]) { if (a[mid] < a[end]) return mid; else if (a[begin] > a[end]) return begin; else return end; } else // a[begin] > a[mid] { if (a[mid] > a[end]) return mid; else if (a[begin] < a[end]) return begin; else return end; } } //定义我们的快速排序 void QuickSort(int* a, int left, int right) { assert(a); if (left >= right) return; int midIndex = GetMidIndex(a, left, right); Swap(&a[midIndex], &a[right]); int prev = left - 1; int cur = left; int keyindex = right; while (cur < right) { if (a[cur] < a[keyindex] && ++prev != cur) Swap(&a[prev], &a[cur]); ++cur; } Swap(&a[++prev], &a[keyindex]); int div = prev; //递归调用 QuickSort(a, left, div - 1); QuickSort(a, div + 1, right); } //定义归并排序版本的外部排序 /第一个参数为第一个要归并的文件，第二个参数为我们第二个要归并的文件 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); } //创建两个临时变量来读取我们文件中的数据 int num1, num2; //fcanf如果读取成功，会生成一个返回值，我们将这个返回值存给我们的临时变量ret1和ret2，用来判断我们的文件中的数据有没有读取成功。 int ret1 = fscanf(fout1, "%dn", &num1); int ret2 = fscanf(fout2, "%dn", &num2); //下面进行归并操作，将我们第一个文件和第二个文件中的内容归入我们第三个文件中 while (ret1 != EOF && ret2 != EOF) { if (num1 < num2) { fprintf(fin, "%dn", num1); ret1 = fscanf(fout1, "%dn", &num1); } else { fprintf(fin, "%dn", num2); ret2 = fscanf(fout2, "%dn", &num2); } } while (ret1 != EOF) { fprintf(fin, "%dn", num1); ret1 = fscanf(fout1, "%dn", &num1); } while (ret2 != EOF) { fprintf(fin, "%dn", num2); ret2 = fscanf(fout2, "%dn", &num2); } //将我们文革代开的文件关闭。 fclose(fout1); fclose(fout2); fclose(fin); } //定义我们归并的主函数 void MergeSortFile(const char* file) { FILE* fout = fopen(file, "r"); if (fout == NULL) { printf("打开文件失败n"); exit(-1); } // 分割成一段一段数据，内存排序后写到，小文件， int n = 10; //这里我们创建一个十个元素的数组，作为我们下面快速排序的文件的对象 int a[10]; int i = 0; int num = 0; char subfile[20]; //这里的filei临时变量是用来记录我们当前所存入的文件编号 int filei = 1; //将我们所开辟的数组中的十个元素全部置空。 memset(a, 0, sizeof(int)*n); //当我们文件读取之后，文件指针是会自己往后移动一个位置的。 while (fscanf(fout, "%dn", &num) != EOF) { //下面我们要将我们的元素十个为一组，存入我们之前开辟的数组中， if (i < n - 1) { a[i++] = num; } else { //当我们十个数据读取完成之后， a[i] = num; //对我们所读取的十个元素进行快速排序 QuickSort(a, 0, n - 1); //这里我们第一个文件时1，第二个文件是2，以此类推 sprintf(subfile, "%d", filei++); //打开我们的刚刚命名的文件，使用fin指针，荡开模式为写入 FILE* fin = fopen(subfile, "w"); if (fin == NULL) { printf("打开文件失败n"); exit(-1); } //将我们之前排序完成的十个数放入我们当前的文件中 for (int j = 0; j < n; j++) { fprintf(fin, "%dn", a[j]); } //关闭我们对文件的读取 fclose(fin); //重置我们的i与拷贝数组 i = 0; memset(a, 0, sizeof(int)*n); } } // 利用互相归并到文件，实现整体有序 char mfile[100] = "12"; char file1[100] = "1"; char file2[100] = "2"; for (int i = 2; i <= n; ++i) { // 读取file1和file2,进行归并出mfile _MergeFile(file1, file2, mfile); strcpy(file1, mfile); sprintf(file2, "%d", i + 1); //这里我们的文件合并是1和2合并后文件名变成12 //12与3合并后变成123，以此类推。 sprintf(mfile, "%s%d", mfile, i + 1); } printf("%s文件排序成功n", file); fclose(fout); } int main() { MergeSortFile("/Users/Documents/filemergesort/SortData.txt"); return 0; }
在我们的最后一个文件中的数据就是我们归并完成之后的结果。
