🔥個人主頁：艾莉絲努力練劍
?專欄傳送門：《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篇，列出來有水字數嫌疑了，就只放指針第六篇的網址，博主在指針（六）把指針部分的前五篇的網址都放在【往期回顧】了，點擊【傳送門】就可以看了）。
大家如果對前面部分的知識點印象不深，可以去上一篇文章的結尾部分看看，博主把需要回顧的知識點相關的博客的鏈接都放在上一篇文章了，上一篇文章的鏈接博主放在下面了：
【數據結構與算法】數據結構初階：詳解順序表和鏈表（三）——單鏈表（上）
結語：本篇文章到這里就結束了，對數據結構的排序知識感興趣的友友們可以在評論區留言，博主創作時可能存在筆誤，或者知識點不嚴謹的地方，大家多擔待，如果大家在閱讀的時候發現了行文有什么錯誤歡迎在評論區斧正，再次感謝友友們的關注和支持！?
的計算流程)
