【外排序】--- 文件归并排序的实现

 Welcome to 9ilk's Code World

       

(๑•́ ₃ •̀๑) 个人主页:        9ilk

(๑•́ ₃ •̀๑) 文章专栏：     数据结构  

我们之前学习的八大排序：冒泡，快排，插入，堆排等都是内排序，这些排序算法处理的都是在内存中的数据，如果我们要处理的数据量过大，不能一次性装进内存中呢？此时我们需要了解我们的新知识 --- 外排序

🏠 什么是外排序

📒 外排序介绍

外排序（External sorting）是指能够处理极⼤量数据的排序算法。

外排序通常采⽤的是⼀种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到⼀个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。然后在归并阶段将这些临时文件组合为⼀个大的有序文件，也即排序结果。

注意：

1. 通常来说，外排序处理的数据不能一次性装入内存，只能放在读写较慢的外存储器(通常是硬盘上)。

2. 我们之前常见的排序是内排，它们排序思想适应的是数据在内存中支持随机访问。归并排序的思想不需要随机访问数据，只需要依次序列读取数据，所以归并排序既是一个内排序，也是一个外排序。

📒 文件归并排序思路分析

   也许有朋友看到文件归并排序会想到，将一个大文件先细分成n个小文件，再各自各自地进行归并，如下图：

这种做法是可行的是但是比较麻烦的是一开始划分小文件的个数以及每个小文件的大小，实现较为复杂，因此我们选择如下的归并思路：

  1.  读取n个值排序后写到file1，再读取n个值排序后写到file2
  2. file1和file2利⽤归并排序的思想，依次读取⽐较，取⼩的尾插到mfile，mfile归并为⼀个有序⽂件
  3. 将file1和file2删掉，mfile重命名为file1
  4. 再次读取n个数据排序后写到file2
  5. 继续⾛file1和file2归并，重复步骤2，直到⽂件中⽆法读出数据。最后归并出的有序数据放到了file1中
动图演示：
这种做法就不需要我们自己去确定划分文件的个数，同时文件大小读取数据固定，而且归并过程中操作文件只有file1 file2这两个文件。

🏠 文件归并排序代码实现

📌 生成大文件

这里我们需要复习C语言库里面的几个关于文件的接口：

fopen  : 打开文件,返回一个FILE*的指针。(const char * filename, const char * mode)

fclose : 关闭文件。( FILE * stream)

fprintf : 将格式化数据写进文件。(FILE * stream, const char * format, ...)

fscanf : 从文件中读取格式化数据。(FILE * stream, const char * format, ...)

具体用法可自行查文档哦 ~

参考代码：

void CreateData()
{FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("fopen fail");return;}const int N = 1000000;srand(time(0));//读入N个数 随机数for (int i = 0; i < N; i++){int num = rand() + i;fprintf(fin, "%d\n", num);}fclose(fin);
}

📌 小文件输入数据并排序

    我们可以利用一个容器利用fscanf从bigfile里读取数据，再用fprintf将读取的数据排序后输入到目标小文件内

//分别读入数据进file1和file2并且排序
void RDatatoSortFile(const char* file1,FILE* bigfile,int n)
{vector<int> v;v.resize(n);FILE* file = fopen(file1, "w");if (file == NULL){perror("fopen fail");return;}//从bigfile读取n个数据进数组for (int i = 0; i < n; i++){int num = 0;fscanf(bigfile, "%d", &num);v.push_back(num);}
//排序sort(v.begin(), v.end());//将数据读入filefor (int i = 0; i < n; i++){fprintf(file, "%d\n", v[i]);}fclose(file);fclose(bigfile);}

注意：

  • 当bigFile里数据要读取完时，读取数据个数可能不足n个数据，这时我们可以利用fscanf的返回值(读到文件末尾->EOF)和一个变量j来判断是否读完了。
  • 同时我们可以修改返回类型为int，当返回0说明文件都读完了。

修改代码：

//分别读入数据进file1和file2并且排序
int RDatatoSortFile(const char* file1,FILE* bigfile,int n)
{vector<int> v;v.resize(n);FILE* file = fopen(file1, "w");if (file == NULL){perror("fopen fail");return;}//从bigfile读取n个数据进数组int j = 0;for (int i = 0; i < n; i++){int num = 0;num = fscanf(bigfile, "%d", &num);if (num == EOF)break;v.push_back(num);j++;}//数据读完提前返回if (j == 0)return 0;sort(v.begin(), v.end());//将数据读入filefor (int i = 0; i < j; i++){fprintf(file, "%d\n", v[i]);}fclose(file);return j;
}

注意：输入完数据后不能先fclose(bigfile),这样会导致bigfile文件指针读到了文件末尾，后续输入不进数据因为一直在文件末尾。

📌 合并file1和file2为mfile

  读取file1和file2内的数据，小的先进mfile继续读取这个文件；最后一定有个文件先读完，将剩下的文件继续读完。

参考代码：

void mergeFile(const char* file1,const char* file2,const char* mfile)
{FILE* File1 = fopen(file1, "r");if (file1 == NULL){perror("fopen fail");return;}FILE* File2 = fopen(file2, "r");if (file2 == NULL){perror("fopen fail");return;}FILE* Mfile = fopen(mfile, "w");if (mfile == NULL){perror("fopen fail");return;}//fscanf读取数据成功都返回的是1 错误返回的是-1 所以要另外开两个变量接收int x1 = 0;int ret1 = 0;ret1 = fscanf(File1, "%d", &x1);int ret2 = 0;int x2 = 0;ret2 = fscanf(File2, "%d", &x2);while (ret1 != EOF && ret2 != EOF){if (x1 <x2){//读进mfilefprintf(Mfile, "%d\n", x1);ret1 = fscanf(File1, "%d", &x1);}else{fprintf(Mfile, "%d\n", x2);ret2 = fscanf(File2, "%d", &x2);}}//没有读完的继续while (ret1 != EOF){fprintf(Mfile, "%d\n", x1);ret1 = fscanf(File1, "%d", &x1);}while (ret2 != EOF){fprintf(Mfile, "%d\n", x2);ret2 = fscanf(File2, "%d", &x2);}//关闭文件fclose(File1);fclose(File2);fclose(Mfile);
}

注意：在从大文件读取数据时，要注意的是，fscanf读取数据成功返回的都是1，因此我们需增设两个变量接收读取到的值。

📌总体逻辑

  • 造大文件
  • 分别从大文件读取数据排序好后输入进file1和file2
  • 将file1和file2合并为mfile
  • 删除file1 file2 ，重命名mfile为file1，继续输入数据进file2
  • 不断重复上述过程直到bigfile数据读取完毕

总体参考代码：

//创建大文件
void CreateData()
{FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("fopen fail");return;}const int N = 100;srand(time(0));//读入N个数 随机数for (int i = 0; i < N; i++){int num = rand() + i;fprintf(fin, "%d\n", num);}fclose(fin);
}//分别读入数据进file1和file2并且排序
int RDatatoSortFile(const char* file1,FILE* bigfile,int n)
{int num = 0;vector<int> v;//注意先提前开空间 因为后面push_back是继续开空间！FILE* file = fopen(file1, "w");if (file == NULL){perror("fopen fail");return 0;}//从bigfile读取n个数据进数组int j = 0;for (int i = 0; i < n; i++){if (fscanf(bigfile, "%d", &num) == EOF)break;v.push_back(num);j++;}//数据读完提前返回if (j == 0)return 0;sort(v.begin(), v.end());//将数据读入filefor (int i = 0; i < j; i++){fprintf(file, "%d\n", v[i]);}fclose(file);//fclose(bigfile);return j;
}void mergeFile(const char* file1,const char* file2,const char* mfile)
{FILE* File1 = fopen(file1, "r");if (file1 == NULL){perror("fopen fail");return;}FILE* File2 = fopen(file2, "r");if (file2 == NULL){perror("fopen fail");return;}FILE* Mfile = fopen(mfile, "w");if (mfile == NULL){perror("fopen fail");return;}//fscanf读取数据成功都返回的是1 错误返回的是-1 所以要另外开两个变量接收int x1 = 0;int ret1 = 0;ret1 = fscanf(File1, "%d", &x1);int ret2 = 0;int x2 = 0;ret2 = fscanf(File2, "%d", &x2);while (ret1 != EOF && ret2 != EOF){if (x1 <x2){//读进mfilefprintf(Mfile, "%d\n", x1);ret1 = fscanf(File1, "%d", &x1);}else{fprintf(Mfile, "%d\n", x2);ret2 = fscanf(File2, "%d", &x2);}}//没有读完的继续while (ret1 != EOF){fprintf(Mfile, "%d\n", x1);ret1 = fscanf(File1, "%d", &x1);}while (ret2 != EOF){fprintf(Mfile, "%d\n", x2);ret2 = fscanf(File2, "%d", &x2);}//关闭文件fclose(File1);fclose(File2);fclose(Mfile);
}int main()
{//CreateData();FILE* bigfile = fopen("data.txt", "r");if (bigfile == NULL){perror("fopen faile");}const char* file1 = "file1.txt";const char* file2 = "file2.txt";const char* mfile = "mfile.txt";int n = 0;cin >> n;//1.先分别将数据读入file1和file2RDatatoSortFile(file1,bigfile,n);RDatatoSortFile(file2, bigfile, n);//2.将file1和file2内容合并进mfile //3.将file1和file2删除 mfile改为file1while (1){mergeFile(file1, file2, mfile);// 删除file1和file2                                                                                                                                                                                                                    remove(file1);remove(file2);//重命名mfile为file1rename(mfile, file1);//归并mfile(file1)和fle2 判断是否读完int num = 0;num = RDatatoSortFile(file2, bigfile, n);if (num == 0)break;}fclose(bigfile);return 0;
}

总结：本节我们学习了用于排序内存不能一次性处理的数据量的排序 --- 外排序，同时根据外排序的原理设计了文件归并排序。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/390471.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

一键生成视频并批量上传视频抖音、bilibili、腾讯（已打包）

一键生成视频并批量上传视频抖音、bilibili、腾讯（已打包）

GenerateAndAutoupload Github地址&#xff1a;https://github.com/cmdch2017/GenerateAndAutoupload 如何下载&#xff08;找到最新的release&#xff09; https://github.com/cmdch2017/GenerateAndAutoupload/releases/download/v1.0.1/v1.0.1.zip 启动必知道 conf.py …
阅读更多...
数论第四节：二元一次不定方程、勾股数

数论第四节：二元一次不定方程、勾股数

不定方程定义 解不确定的方程称为不定方程。一般化的定义为&#xff1a;不定方程是指未知数的个数多余方程的个数&#xff0c;或未知数受到某种限制&#xff08;如整数、正整数等&#xff09;的方程和方程组。 二元一次不定方程定义 形如axbyc的形式的方程。其中a,b不等于0&…
阅读更多...
Qt对象树的介绍

Qt对象树的介绍

目录 创建项目&#xff08;此处我就不多介绍了&#xff09; 按钮 对象树 创建项目&#xff08;此处我就不多介绍了&#xff09; QMainWidow带菜单栏的 QWidget空白的 QDialog对话框 创建功能时注意&#xff1a; 项目工程名称一般不要有标点&#xff0c;不要带中文 按钮 /…
阅读更多...
变量作用域、作用域链、return

变量作用域、作用域链、return

全局变量 全局变量因为在全局操作会每次留存上次操作的结果 局部变量因为执行完成就会被销毁并不会保留本次操作的结果 可以通过传参和返回&#xff0c;将结果不断地专递处理 局部变量 参数也是局部变量 函数内的预解析预赋值 函数内的局部变量 如果同名全局变量遇到局部变量…
阅读更多...
linux进程控制——进程替换——exec函数接口

linux进程控制——进程替换——exec函数接口

前言&#xff1a; 本节内容进入linux进程控制板块的最后一个知识点——进程替换。 通过本板块的学习&#xff0c; 我们了解了进程的基本控制方法——进程创建&#xff0c; 进程退出&#xff0c; 进程终止&#xff0c; 进程替换。 进程控制章节和上一节进程概念板块都是在谈进程…
阅读更多...
【IEEE出版】第五届大数据、人工智能与软件工程国际研讨会（ICBASE 2024，9月20-22）

【IEEE出版】第五届大数据、人工智能与软件工程国际研讨会（ICBASE 2024，9月20-22）

第五届大数据、人工智能与软件工程国际研讨会&#xff08;ICBASE 2024&#xff09;将于2024年09月20-22日在中国温州隆重举行。 会议主要围绕大数据、人工智能与软件工程等研究领域展开讨论。会议旨在为从事大数据、人工智能与软件工程研究的专家学者、工程技术人员、技术研发人…
阅读更多...
C#加班统计次数

C#加班统计次数

C#加班统计次数 运行环境&#xff1a;vs2022 .net 8.0 社区版 1、用C#语言&#xff1b;2、有界面上传Excel文件; 3、对Excel列&#xff08;部门、人员姓名、人员编号、考勤时间 &#xff09;处理&#xff1a;&#xff08;1&#xff09;按人员编号、考勤日期分组且保留原来字段&…
阅读更多...
18 栈的属性，函数调用

18 栈的属性，函数调用

阅读更多...
大厂linux面试题攻略五之数据库管理

大厂linux面试题攻略五之数据库管理

一、数据库管理-MySQL语句 0.MySQL基本语句&#xff1a; 1.SQL语句-增 创建xxx用户&#xff1a; mysql>create user xxx % indentified by 123456; xxx表示用户名 %b表示该用户用来连接数据库的方式&#xff08;远程或本地连接&#xff09; indentified by 123456设置密码…
阅读更多...
C语言基础知识之函数指针和指针函数

C语言基础知识之函数指针和指针函数

函数指针和指针函数 函数指针和指针函数指向函数的指针返回指针值的函数指针函数和函数指针的区别 问题1_1代码1_1结果1_1 函数指针和指针函数 指向函数的指针 用函数指针变量调用函数 可以用指针变量指向整型变量、字符串、数组&#xff0c;也可以指向一个函数。一个…
阅读更多...
Xinstall超级渠道功能，轻松解决App推广中的层级统计难题

Xinstall超级渠道功能，轻松解决App推广中的层级统计难题

随着互联网的不断发展和流量玩法的多样化&#xff0c;App推广和运营面临着前所未有的挑战。传统的营销方式在互联网流量红利衰退的背景下逐渐失效&#xff0c;企业急需提高获客转化的效率和用户留存。在这个过程中&#xff0c;App渠道数据分析显得尤为重要。然而&#xff0c;许…
阅读更多...
Spring中是如何实现IoC和DI的？

Spring中是如何实现IoC和DI的？

前言&#xff1a;在前一篇文章中对于IoC的核心思想进行了讲解&#xff0c;而本篇文章则从Spring的角度入手&#xff0c;体会Spring对于IoC是如何实现的。 如果对IoC还有不太了解的可以阅读上一篇文章&#xff0c;相信一定会带来全新的收获&#xff1a;什么是IoC&#xff08;控制…
阅读更多...
J029_UDP通信

J029_UDP通信

一、需求描述 实现UDP的通信 1.1 一发一收 1.1.1 ClientTest1 package com.itheima.udp;import java.net.*;import static java.net.InetAddress.*;//完成udp通信快速入门&#xff0c;实现一收一发 public class ClientTest1 {public static void main(String[] args) thro…
阅读更多...
【数据结构之单链表的实现（不带头）】

【数据结构之单链表的实现（不带头）】

1.单链表 1.1概念与结构 链表是一种物理存储结构上非连续&#xff0c;非顺序的存储结构&#xff0c;数据元素的逻辑顺序是通过链表中的指针连接次序实现的。 可以用下图便于理解 节&#xff08;结&#xff09;点&#xff1a; 与顺序表不同的是&#xff0c;链表里面的每节“车…
阅读更多...
NRK3301识别语音芯片在智能按摩椅中的应用与体验提升

NRK3301识别语音芯片在智能按摩椅中的应用与体验提升

在健康与舒适日益受到关注的今天&#xff0c;按摩椅作为缓解疲劳、舒缓压力的设备受到了广大消费者的喜爱。然而&#xff0c;传统的按摩椅操作方式往往繁琐且不直观。在这一背景下&#xff0c;NRK3301语音识别芯片的应用为按摩椅带来了新的变革。‌ 一、高识别准确率和快速响应…
阅读更多...
halcon深度学习语义分割预处理图片遇到的坑

halcon深度学习语义分割预处理图片遇到的坑

1.最近使用halcon深度学习语义分割&#xff0c;做缺陷检测。 2.在使用halcon的深度学习标准工具&#xff0c;标注图片 3.标注好图片后&#xff0c;到处预处理&#xff0c;发现报错&#xff0c;[‘Multiple matching segmentation files for image /1.jpg’]意思是:[’ image /…
阅读更多...
二十天刷leetcode【hot100】算法- day1[前端Typescript]

二十天刷leetcode【hot100】算法- day1[前端Typescript]

哈希表 1. 两数之和 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是&#xff0c;数组中同一个元素在答案里不能重复出现。你…
阅读更多...
go语言day21 goland使用gin框架、gorm框架操作mysql数据库redis数据库 使用宝塔创建redis数据库

go语言day21 goland使用gin框架、gorm框架操作mysql数据库redis数据库 使用宝塔创建redis数据库

GORM 指南 | GORM - The fantastic ORM library for Golang, aims to be developer friendly. gorm package - github.com/jinzhu/gorm - Go Packages go语言day20实现投票功能项目包-CSDN博客 gin框架标准项目结构&#xff1a; models&#xff1a;存放对应实体类和gorm包增删…
阅读更多...
DVWA（SQL注入）medium、high

DVWA（SQL注入）medium、high

medium &#xff08;1&#xff09;判断注入是字符型还是数值型 数值型&#xff0c;获得了用户信息。 id 1 or 11 &#xff08;2&#xff09;查询字段数 为3时报错&#xff0c;代表字段数为2。 1 order by 3 &#xff08;3&#xff09;显示字段顺序 1 union select 1,2 &…
阅读更多...
机器学习练手（三）：基于决策树的iris 多分类和波士顿房价预测

机器学习练手（三）：基于决策树的iris 多分类和波士顿房价预测

总结&#xff1a;本文为和鲸python 可视化探索训练营资料整理而来&#xff0c;加入了自己的理解&#xff08;by GPT4o&#xff09; 原活动链接 原作者&#xff1a;vgbhfive&#xff0c;多年风控引擎研发及金融模型开发经验&#xff0c;现任某公司风控研发工程师&#xff0c;对…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发