当前位置：首页 > news >正文

【数据结构与算法】数据结构初阶：排序内容加餐（二）——文件归并排序思路详解（附代码实现）

news 2025/8/4 9:56:52

🔥个人主页：艾莉丝努力练剑

❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题

🍉学习方向：C/C++方向

⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

这个用来测试代码的对比排序性能的代码博主依然还是附在下面，大家可以对比一下各种排序算法的运行时间，从而对不同排序方法的时间复杂度有更加直观地认识：

//测试排序的性能对比  
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}//begin和end的时间差就是int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}

前言：本篇文章，我们继续来介绍排序相关拓展的加餐部分的知识点，在初阶的数据结构与算法阶段，我们把知识点分成三部分，复杂度作为第一部分，顺序表和链表、栈和队列、二叉树为第二部分，排序为第二部分，我们之前已经介绍完了第一部分：算法复杂度和第二部分：顺序表和链表、栈和队列、二叉树。本文我们继续学习第三部分中的排序的内容。

正文

一、文件归并排序思路

1、了解外排序

2、文件归并排序的思路

二、文件归并排序代码实现

结尾

正文

本文和上一篇文章属于是加餐，大家先掌握排序的主线内容再来看这些比较好。

先掌握排序数据结构的主线内容——插入排序、选择排序、交换排序、归并排序——再来看加餐。

上篇文章链接放在这里，当然结尾照例也挂了链接：

【数据结构与算法】数据结构初阶：排序内容加餐（一）——快速排序：三路划分、自省排序【数据结构与算法】数据结构初阶：排序内容加餐（一）——快速排序：三路划分、自省排序

一、文件归并排序思路

1、了解外排序

2、文件归并排序的思路

画图理解：

二、文件归并排序代码实现

以下是文件归并排序代码实现——

代码实现：

#define  _CRT_SECURE_NO_WARNINGS  1
#include<stdio.h>
#include<time.h>
#include<stdlib.h>//创建N个随机数，写到文件中
void CreatNData()
{//造数据int n = 10000000;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 compare(const void* a, const void* b)
{return(*(int*)a - *(int*)b);
}//返回实际读到的数据个数，没有数据了返回0
int ReadNDataSortToFile(FILE* fout, int n, const char* file1)
{int x = 0;int* a = (int*)malloc(sizeof(int) * n);if (a == NULL){perror("malloc error");return 0;}//想读取n个数据，如果遇到文件结束，应该读到j个int j = 0;for (int i = 0; i < n; i++){if (fscanf(fout, "%d", &x) == EOF)break;a[j++] = x;}if (j == 0){free(a);return 0;}//排序qsort(a, j, sizeof(int), compare);FILE* fin = fopen(file1, "w");if (fin == NULL){free(a);perror("fopen error");return 0;}//写回file1文件for (int i = 0; i < j; i++){fprintf(fin, "%d\n", a[j]);}free(a);fclose(fin);return j;
}void MergeFile(const char* file1, const char* file2, const char* mfile)
{FILE* fout1 = fopen(file1, "r");if (fout1 == NULL){perror("fopen error");return;}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){perror("fopen error");return;}FILE* mfin = fopen(mfile, "w");if (mfin == NULL){perror("fopen error");return;}//归并逻辑int x1 = 0;int x2 = 0;int ret1 = fscanf(fout1, "%d", &x1);int ret2 = fscanf(fout2, "%d", &x2);while (ret1 != EOF && ret2 != EOF){if (x1 < x2){fprintf(mfin, "%d\n", x1);ret1 = fscanf(fout1, "%d", &x1);}else{fprintf(mfin, "%d\n", x2);ret2 = fscanf(fout2, "%d", &x2);}}while (ret1 != EOF){fprintf(mfin, "%d\n", x1);ret1 = fscanf(fout1, "%d", &x1);}while (ret2 != EOF){fprintf(mfin, "%d\n", x2);ret2 = fscanf(fout2, "%d", &x2);}fclose(fout1);fclose(fout2);fclose(mfin);
}int main()
{CreatNData();const char* file1 = "file1.txt";const char* file2 = "file1.txt";const char* mfile = "file1.txt";FILE* fout = fopen("data.txt", "r");if (fout == NULL){perror("fopen error");return;}int m = 1000000;ReadNDataSortToFile(fout, m, file1);ReadNDataSortToFile(fout, m, file2);while (1){MergeFile(file1, file2, mfile);//删除file1和file2remove(file1);remove(file2);//重命名mfile为file1rename(mfile, file1);//当再去读取数据，一个都读不到，说明此时已经没有数据了//已经归并完成，归并结果在file1int n = 0;if ((n = ReadNDataSortToFile(fout, m, file2)) == 0)break;//if (n < 100)//{//	int x = 0;//}}return 0;
}

注意：下图这里的m不要看错，一定要擦亮眼睛，铸币博主没注意，在这里写了个100，1000000个数据跑得那速度让铸币主包怀疑自己的电脑被夺舍了，主包还以为1946年那台世界上第一台计算机“埃尼阿克”的幽灵把主包电脑摄魂了，没想到是主包一开始测试的时候在这里写了个100忘记改掉了。。。大家不要犯跟博主一样的错误。

结尾

往期回顾：

本期内容需要回顾的C语言知识如下面的截图中所示（指针博主写了6篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了）。

大家如果对前面部分的知识点印象不深，可以去上一篇文章的结尾部分看看，博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了，上一篇文章的链接博主放在下面了：

【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）