【初阶数据结构】 升沉有序的平仄 排序 3

点击展开/收起 文章目录文章目录本节内容简介归并排序(外排序)外排序的意义以及原理1. 生成随机数据(data.txt)2. 取n个数据排好序到文件中3. 归并文件4. 文件归并排序计数排序下面我来总结一下各大排序的稳定性与时间复杂度在这里我们也是终于结束了排序结束了我们的初阶数据结构的章节道阻且长我们还需努力下一章节我会开启C感谢大家的支持希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力前言 许多人认为排序只是内存中的数据游戏但在面对海量数据吞吐时内排序往往因物理内存窒息而无能为力。本文将带你跳出内存舒适区手撕基于磁盘 I/O 的归并外排序External Merge Sort。本文不仅包含硬核的 C 语言文件流操作与计数排序实现更会向下延伸至计算机底层操作系统与硬件架构深度复盘 Windows 资源管理器的异步刷新机制以及 SSD 固件层面的 TRIM 指令、垃圾回收和磨损均衡原理本节内容简介计划任务外排序归并硬盘删除原理讲解计数排序总结各大排序的时间复杂度和稳定性归并排序(外排序)外排序的意义以及原理其实我们的排序是分为内排序外排序的,内排序 : 在内存中排序外排序 : 要在硬盘操纵如今我们学的排序中只有归并是外排序外排序的意义但数据量巨大的时候,超过分派的内存大小,这时候就是外排序发力的时候文件归并排序思路:这里需要四个文件,data.txt(原始数据) file1.txt, file2.txt, mfile.txt1. 生成随机数据(data.txt)我这里造数据只在注释里面略讲,详细步骤请去下面链接创造数据的讲解,堆排序voidCreatData(intn){constchar*filedata.txt;FILE*finfopen(file,w);//这里w是双引号if(finNULL){perror(fopen fail);exit(-1);}for(inti0;in;i){intxrand()%10000i;//注意这里写文件要在每个数据后面加\n不加的话,存入文件中间数据会连成一片,无法正确读取fprintf(fin,%d\n,x);}// 打开文件之后不要忘记关闭文件fclose(fin);}2. 取n个数据排好序到文件中解读一下这里的参数,这里FILE* fout是在void MergeFileSort(const char* data, int n)中打开的data.txt传入这个是为了在上次读的数据基础上,继续往读数据,a是数组,用于存放每次读到的N个数据,得到之后排序,再往传入的file中间写const char* file是读取N个数据排序好,存入这个文件中int n每次都读n个数据当然这里可能会遇到一个问题,加入读不到N个数据,data中没有足够N个数据的量咋办?这就是我们给个返回值的好处,每次返回读到的数据个数下面是fscanf返回值的文档表述这里我建议大家去查英文文档,不会的单词可以自己查,不要机翻,程序员是因该会看英文文档的,在后面的C部分我会经常给大家展示英文文档下面是原文档链接大家可以自己进去看看C/C英文文档这段英文讲的是什么呢?返回值是成功匹配并赋值的输入项个数举个例子fscanf(fp, %d %s, n, str)如果成功读入一个整数和一个字符串返回 2如果只成功读入整数第二个匹配失败返回 1如果第一个匹配就失败返回 0如果遇到文件末尾或发生输入错误返回 EOF通常为 -1利用fscanf返回值只要没读到文件末尾我numnum就可以做计数器来记录读入了多少个数据在进行我文件操作别忘记关闭文件,打开文件要进行检查与malloc类似intReadNDataToFile(FILE*fout,constchar*file,intn,int*a){intnum0;intx;//利用fscanf返回值只要没读到文件末尾我numnum就可以做计数器来记录读入了多少个数据while(numnfscanf(fout,%d,x)!EOF){a[num]x;}if(num0)return0;//排序数据HeapSort(a,num);//打开文件FILE*finfopen(file,w);if(finNULL){perror(fopen fail);exit(-1);}//向文件file中写入读到的num个数据for(inti0;inum;i){fprintf(fin,%d\n,a[i]);}//关闭文件fclose(fin);returnnum;}3. 归并文件voidMergeFile(constchar*file1,constchar*file2,constchar*mfile){//打开三个文件FILE*fout1fopen(file1,r);FILE*fout2fopen(file2,r);FILE*mfinfopen(mfile,w);intret1,ret2,x1,x2;//接收返回值如果读到文件末尾只要有一个文件读到文件末尾就跳出循环ret1fscanf(fout1,%d,x1);ret2fscanf(fout2,%d,x2);while(ret1!EOFret2!EOF){if(x1x2){fprintf(mfin,%d\n,x2);ret2fscanf(fout2,%d,x2);}else{fprintf(mfin,%d\n,x1);ret1fscanf(fout1,%d,x1);}}//将剩余一个文件中剩余数据写入文件mfilewhile(ret1!EOF){fprintf(mfin,%d\n,x1);ret1fscanf(fout1,%d,x1);}while(ret2!EOF){fprintf(mfin,%d\n,x2);ret2fscanf(fout2,%d,x2);}//记得关闭文件fclose(fout1);fclose(fout2);fclose(mfin);}4. 文件归并排序核心部分先归并两文件移除flie1,file2重名名mflie为file1循环终止条件ReadNDataToFile(fout, file2, m,a) 0我们设计返回值就起作用了当不再能从data中读到数据证明我们把它读完了这里要用到几个没见过的函数这里传参很简单我就不讲了也很好理解while (1) { MergeFile(file1, file2, mfile); remove(file1); remove(file2); rename(mfile, file1); if (ReadNDataToFile(fout, file2, m,a) 0) break; }voidMergeFileSort(constchar*data,intn){srand((unsignedint)time(0));FILE*foutfopen(data,r);if(foutNULL){perror(fopen fail);exit(-1);}//设置每次读入数据的量intm1000000;int*a(int*)malloc(m*sizeof(int));if(aNULL){perror(malloc fail);exit(-1);}//给文件命名constchar*file1file1.txt;constchar*file2file2.txt;constchar*mfilemfile.txt;//第一次写入数据ReadNDataToFile(fout,file1,m,a);ReadNDataToFile(fout,file2,m,a);while(1){MergeFile(file1,file2,mfile);remove(file1);remove(file2);rename(mfile,file1);//循环终止条件if(ReadNDataToFile(fout,file2,m,a)0)break;}//关闭文件,释放开的空间free(a);fclose(fout);}我在观察文件归并时发现了一个问题每次读的数据量越大文件归并排序就越快而且在不同数据量下有些文件会出现有些文件不会出现我开始以为我写错代码逻辑了但是我去查了一下资料并不是我写错逻辑出现这种现象的原因是文件打开/关闭的次数和 Windows 文件资源管理器刷新频率之间的关系。当每次读入的数据量小比如 10 万条 → 归并轮数多 → 你需要反复打开、关闭、删除、重命名文件然而最费时间的就是文件打开与关闭内部那些排序反而并不是很费时间在内存中排100万数据与排10万个数据区别不大都是一瞬间的事情主要还是打开与关闭文件Windows 资源管理器的刷新不是实时它的刷新间隔通常是 几百毫秒到几秒。你能看见中间文件不是因为操作慢而是因为操作次数多且分布在较长的时间轴上刚好撞上了 Windows 的定时刷新你看不见是因为操作次数太少、太快刷新还没来得及“拍照”就已经结束了。每次读写文件时的打开关闭文件都是在留时间给Windos文件资源管理器来刷新文件来给你看到因此你看到的那些文件不是是实时文件状态只是某个时间的一张快照m100000每次读一百万个数据m100000每次读十万个数据m100000每次读十万个数据由此我延伸又问了deepseek一些问题我问他remove是真正把数据删除了吗物理消失了吗一. 机械硬盘逻辑上是“真删除”这和你用 ShiftDelete 直接删除文件是一样的文件路径会立即从文件系统中“消失”自然也不会进入回收站所以你用常规方法找不到它。物理上可能是“假删除”文件路径虽然看不见了但只要磁盘空间没被新数据覆盖通过专业数据恢复软件就能找回来。这是因为 remove 只是在硬盘的“目录”上做了个标记告诉系统这个位置的数据可以覆盖了。上面只是我了解到的浅薄知识如有不对请批评在电脑中我们多了一步回收站回收站就不会标记成可用,为了让你反悔恢复文件他暂时不让那片空间可用你可以做个实验你把1G数据的文件手动删除到回收站你会发现那个硬盘上可用空间没有增大但你从回收站把该文件彻底删除他就会增大二. SSD硬盘TRIM指令当你删除文件时操作系统会立刻发送TRIM指令给SSD。SSD收到后实际擦除那些闪存块中的数据标记为无效并立即回收。所以文件数据可能在几毫秒内就被物理擦除不再像机械硬盘那样“只改标记、数据暂留”。写入放大与垃圾回收SSD不能覆盖写必须先擦除整个块才能写入新数据。为了性能SSD固件会后台做垃圾回收——提前把无效页擦除。这意味着删除操作很可能被立即执行物理擦除。磨损均衡为了延长寿命SSD会把数据分布在不同的闪存单元。即使你只删除一个小文件它可能早已被移动过多次删除后原始位置的数据也可能被其他数据覆写。结果在SSD上误删文件后恢复成功率远低于机械硬盘。因为数据可能已被TRIM和垃圾回收彻底清除。恢复工具往往无法直接读取被TRIM过的块SSD返回的全是0。只有极少数专业实验室能在SSD主控层面尝试恢复成本极高。由此我们想想这样有什么应用呢数据恢复别再花很多钱去找电脑维修店脑版恢复数据了既然你了解到了有这些原理恢复数据也就不神奇了市面上有很多成熟免费的软件下面分享一下– Recuva个人使用完全免费界面友好有深度扫描模式。适合恢复误删的照片、文档。– TestDisk PhotoRec开源免费功能极为强大。TestDisk 擅长恢复分区表、修复启动扇区PhotoRec 则是“签名恢复”的典范——它不管你原来是什么文件系统直接根据文件头尾去硬盘里捞数据。你在课堂上学的“文件有固定头部”这一点就是 PhotoRec 的工作基础。注意既然了解到原理你误删文件尽量越早恢复文件越好因为文件位置被复写了就不好恢复了另外SSD硬盘删除机制更复杂不易恢复steam第一次下载过的游戏第二次下载会很快在steam他会有depotcache一些游戏缓存你删除了游戏这些缓存还在你电脑里面重复下载就会很快计数排序简单来说计数排序就是造出来一个初始化为零的数组等遍历原数组大小与原数组大小一致的就在计数数组对应下标位置加1类似于下图但问题应运而生如果这样的话数组下标代表值空间复杂度就高了那他是怎么排序的有了计数数组原来每个值在count[]数组中都标记有位置而且是按有序排列我们遍历count数组如果为零我就跳过大于零我就取她的下标放到我这个位置如下图动画他的时间复杂度是ON,但也有极大的局限性如果1100000这种相差巨大的数据她的空间就开得很大浪费空间因此他很不常用voidCountSort(int*a,intn){intmax,min,i;maxmina[0];for(i0;in;i){if(a[i]max){maxa[i];}if(a[i]min){mina[i];}}intrangemax-min1;int*count(int*)calloc(range,sizeof(int));if(countNULL){perror(calloc fail);return;}for(i0;in;i){count[a[i]-min];}i0;for(intj0;jrange;j){while(count[j]--){a[i]jmin;}}free(count);}下面我来总结一下各大排序的稳定性与时间复杂度首先解释一下稳定性排序的稳定性是指在待排序的序列中如果存在两个相等的元素比如两个人都叫“张三”或者两个数值都是 5排序后它们原来的相对前后顺序保持不变。简单说稳定排序不会打乱原本相等元素之间的次序不稳定排序可能会打乱。在这里我们也是终于结束了排序结束了我们的初阶数据结构的章节道阻且长我们还需努力下一章节我会开启C感谢大家的支持希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力