外排序中的归并排序

外排序中的归并排序

  • 7.11 外排序中的归并排序
    • 相关基础知识
    • 原理
    • 最终参考程序

7.11 外排序中的归并排序

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。（下文也称外排序）

例如 1 G = = 102 4 3 b y t e 1G==1024^3 byte 1G==10243byte，一个int型整数4byte，100亿（ 1 0 10 10^{10} 1010）个int型整数占用空间为37G左右，针对这100亿个数据的排序已无法用常见的排序算法去操作。因为内存无法容纳如此庞大的数据，这些数据必定是保存在磁盘中。

归并排序是将数据分割成若干个细小的单位，再将这些细小的单位合并成一个整体，合并的时候按照某种排序规则进行。所以归并排序不仅可以做内排序，还能充当外排序的重要角色。

相关基础知识

外排序是针对文件操作的，所以需要掌握和文件相关的函数和命令。

测试环境是windows 11，所以命令以windows 11适用为主。

可能用到的：

  1. int scanf(const char* format[,argument]...);

scanf能将从键盘上读取的数据存放进变量。

  1. int fscanf(FILE* stream , const char* format[, argument ]...);

fscanf功能和scanf类似，但不同的是fscanf可以指定操作文件也就是形参stream。当stream为stdin（标准输入流）时和scanf几乎无区别。

  1. int sscanf(const char* buffer,const char* format[,argument] ...);

sscanf将数据读取对象从文件变成了指定字符串。

  1. int printf(const char* format [,argument*]*... );

printf能将数据以字符串的形式打印在终端控制台（windows叫cmd）。

  1. int fprintf(FILE* stream,const char* format[,argument*]*...);

fprintf能将数据以字符串的形式打印在指定文件。当stream为stdout（标准输出流）时和printf几乎无区别。

  1. int sprintf(const char* buffer,const char* format[,argument*]*...);

sprintf将数据输出的对象从文件变成了字符串。

  1. FILE* fopen(const char* filename,const char* mode);

返回文件filename的操作模式为mode的文件指针。

  1. int system(const char* command);

system能调用命令行让cmd执行各种操作。

  1. int snprintf(char* s,size_t n,const char *format,...);

和sprintf相比，它能指定输出n个字符到字符串s，并返回成功输出的字符数。于是我们可以这样操作：int name_len = snprintf(NULL,0,"midFile_%d_%d.txt",level,fnum);，这个函数可以返回文件名的长度，因为是指定输出0个字符到NULL地址处的“字符串”，所以函数内部并没有产生实质性的指针调用操作。

  1. windows OS，cmd的命令：

    1. move src dis 将src路径的某文件改名并移动到dis路径。
    2. del file 删除file文件。
    3. md route 创建路径（目录）。
    4. rd route 删除路径（目录）。

原理

  1. 将数据存放在一个可读的文本文件中（其他拓展名的应该也行，关键是程序和自己都能识别）。
  2. 读取这个文件的数据，读完一段数据之后，用内排序处理，将处理完的数据输出为中间文件。

中间文件的命名不唯一，我选择的格式是midFile_level_num.txt，level是级别，num是文件的编号，这样以来，每个level级的中间文件都是由level-1级的文件合并而来。

中间文件最好放在一个文件夹中统一保存。

  1. 将所有的中间文件两两归并，生成更高一级的中间文件，并删除参与归并的低一级的文件（磁盘容量充裕的话可忽略）。

偶数个中间文件归能全部归并完成并删除，奇数个中间文件会留一个，那个文件改名成高一级的中间文件即可。

  1. 重复3的操作，直到只剩最后一个文件，那个文件即为排序好的数据。

原理其实和归并排序差不多，但有磁盘作为存储数据的介质，可操作空间非常大。
请添加图片描述

最终参考程序

fileSort.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

typedef int Datatype;

//创造数据
void createData(int num);

//判断数据是否有序
int judgSort(Datatype* a, int n);

//用归并算法将文件中的数据进行排序
void mergeSortFile(const char* st);

fileSort.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"fileSort.h"

//交换函数
void Swap(Datatype* a, Datatype* b) {
	int t = *a;
	*a = *b;
	*b = t;
}

//创造数据
void createData(int num) {
	srand((size_t)(0));
	char st[] = "beforeSortData.txt";
	FILE* fout = fopen(st, "w");
	int i = 0;
	for (i = 0; i < num; i++)
		fprintf(fout, "%d\n", rand() * rand() + 1);
	fclose(fout);
}

//判断数据是否有序
int judgSort(Datatype* a, int n) {
	int i = 0;
	for (i = 0; i < n - 1; i++)
		if (a[i] > a[i + 1])
			break;
	return i == n - 1;
}

//插入排序
void insertSort(Datatype* a, int n) {
	int i = 0;
	for (i = 0; i < n - 1; ++i) {
		int end = i;
		int tmp = a[i + 1];

		while (end >= 0) {
			if (a[end] > tmp) {
				a[end + 1] = a[end];
				--end;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}
}

//生成中间文件
void buyMidFile(Datatype* a, int n, int level, int* fnum) {
	int nlen = 64;//中间文件名字最大长度
	char* midFileName = (char*)malloc(sizeof(char) * nlen);
	if (midFileName == NULL) {
		printf("buyMidFile malloc 1");
		perror("");
		exit(-1);
	}

	//生成1个文件数，计数变量增加
	(*fnum)++;
	//文件名长度
	int flen = snprintf(NULL, 0,
		".\\sub\\midFile_%d_%d.txt", level, *fnum);
	while (flen > nlen) {
		char* tmp = (char*)realloc(midFileName, nlen * 2 * sizeof(char));
		if (tmp == NULL) {
			printf("buyMidFile realloc 2");
			perror("");
			exit(-1);
		}
		midFileName = tmp;
		nlen *= 2;
	}

	flen = sprintf(midFileName,
		".\\sub\\midFile_%d_%d.txt", level, *fnum);
	FILE* fout = fopen(midFileName, "w");
	if (fout == NULL) {
		system("md sub");//可能是文件夹不存在的情况
		fout = fopen(midFileName, "w");
		if (fout == NULL) {
			printf("%s打开失败", midFileName);
			exit(-1);
		}
	}

	int i = 0;
	for (i = 0; i < n; i++)
		fprintf(fout, "%d\n", a[i]);


	free(midFileName);
	fclose(fout);
}

//切割文件
int inciseFile(const char* st) {
	//打开源文件
	FILE* srcData = fopen(st, "r");
	if (srcData == NULL) {
		printf("%s打开失败", st);
		exit(-1);
	}

	//申请数组
	Datatype* a = (Datatype*)malloc(sizeof(Datatype) * 10);
	if (a == NULL) {
		printf("inciseFile malloc 1");
		perror("");
		exit(-1);
	}
	int ai = 0;//和a配套的指针变量
	int srcp = 0;//文件阅读进度标记
	int tnum = 0;//临时变量
	int fnum = 0;//生成的文件数
	while (srcp = fscanf(srcData, "%d", &tnum), srcp != EOF) {
		a[ai++] = tnum;
		if (ai == 10) {//读满10就排序
			insertSort(a, ai);
			buyMidFile(a, ai, 1, &fnum);
			ai = 0;
		}
	}
	if (ai != 0) {
		insertSort(a, ai);
		buyMidFile(a, ai, 1, &fnum);
		ai = 0;
	}
	return fnum;
}

//归并文件
int mergeFile(int level, int last_num) {
	int this_num = 0;//记录这一层生成的文件数
	FILE* file1 = NULL, * file2 = NULL;//参与归并的两个文件

	int fnlen = 64;//文件名的最大长度
	char* file_name = (char*)malloc(sizeof(char) * fnlen);
	if (file_name == NULL) {
		printf("mergeFile malloc 1");
		perror("");
		exit(-1);
	}

	int i = 1;
	int n1 = 0, n2 = 0, p1 = 0, p2 = 0;//临时变量n，文件阅读追踪变量p
	for (i = 1; i < last_num; i += 2) {//枚举上一层的文件
		int name_len =
			snprintf(NULL, 0,
				"sub\\midFile_%d_%d.txt", level - 1, i);

		//扩容兼检查容量
		while (fnlen < name_len) {
			char* tmp = (char*)realloc
			(file_name, fnlen * 2 * sizeof(char));
			if (tmp == NULL) {
				printf("mergeFile realloc 2");
				perror("");
				exit(-1);
			}
			file_name = tmp;
			fnlen *= 2;
		}

		//打开三个要操作的文件
		sprintf(file_name, "sub\\midFile_%d_%d.txt", level - 1, i);
		file1 = fopen(file_name, "r");
		if (file1 == NULL) {
			printf("%s打开失败", file_name);
			exit(-1);
		}

		sprintf(file_name, "sub\\midFile_%d_%d.txt", level - 1, i + 1);
		file2 = fopen(file_name, "r");
		if (file2 == NULL) {
			printf("%s打开失败", file_name);
			exit(-1);
		}

		sprintf(file_name, "sub\\midFile_%d_%d.txt", level, ++this_num);
		FILE* final_file = fopen(file_name, "w");
		if (final_file == NULL) {
			printf("%s打开失败", file_name);
			exit(-1);
		}

		//文件归并
		p1 = fscanf(file1, "%d", &n1);
		p2 = fscanf(file2, "%d", &n2);
		while (p1 != EOF && p2 != EOF) {
			if (n1 < n2) {
				fprintf(final_file, "%d\n", n1);
				p1 = fscanf(file1, "%d", &n1);
				//读完最后一个数后p1即为EOF，
				//若不加，则少读1个数据
			}
			else {
				fprintf(final_file, "%d\n", n2);
				p2 = fscanf(file2, "%d", &n2);
			}
		}
		while (p1 != EOF) {
			fprintf(final_file, "%d\n", n1);
			p1 = fscanf(file1, "%d", &n1);
		}
		while (p2 != EOF) {
			fprintf(final_file, "%d\n", n2);
			p2 = fscanf(file2, "%d", &n2);
		}

		fclose(file1);
		fclose(file2);
		file1 = file2 = NULL;
		fclose(final_file);

		//删除上一级的中间文件
		sprintf(file_name, "del .\\sub\\midFile_%d_%d.txt", level - 1, i);
		system(file_name);
		sprintf(file_name, "del .\\sub\\midFile_%d_%d.txt", level - 1, i + 1);
		system(file_name);
	}

	//处理奇数个中间文件的情况
	if (i == last_num) {
		int name_len = snprintf(NULL, 0, 
			"move .\\sub\\midFile_%d_%d.txt .\\sub\\midFile_%d_%d.txt",
			level - 1, i, level, ++this_num);
		while (fnlen < name_len) {
			char* tmp = (char*)realloc
			(file_name, fnlen * 2 * sizeof(char));
			if (tmp == NULL) {
				printf("mergeFile realloc 2");
				perror("");
				exit(-1);
			}
			file_name = tmp;
			fnlen *= 2;
		}

		sprintf(file_name,
			"move .\\sub\\midFile_%d_%d.txt .\\sub\\midFile_%d_%d.txt",
			level - 1, i, level, this_num);
		system(file_name);
	}

	free(file_name);
	return this_num;
}

//用归并算法将文件中的数据进行排序
void mergeSortFile(const char* st) {
	//1、将文件分割10个为1组的多个小文件。
	int last_num = inciseFile(st);//last num

	//2、两个文件归并成一个，变归并边删除子文件。
	int level = 2;//这一层的文件数，等级
	while (last_num > 1) {
		last_num = mergeFile(level, last_num);//归并生成的等级，上层文件数
		++level;
	}
	//3、归并到最后一个，再将文件改名
	int len = snprintf(NULL, 0, 
		"move .\\sub\\midFile_%d_1.txt .\\afterSortData.txt", level - 1);
	char* tmp = (char*)malloc(sizeof(char) * len);
	if (tmp == NULL) {
		printf("mergeSortFile malloc 1");
		perror("");
		exit(-1);
	}
	sprintf(tmp, 
		"move .\\sub\\midFile_%d_1.txt .\\afterSortData.txt", 
		level - 1);
	system(tmp);
	system("rd sub");
	printf("beforeSortData.txt排序成功\n");
}

test.c

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif

#include"FileSort.h"

void f0() {//生成随机数文件
	createData(114514);
}

void f1() {//文件归并
	mergeSortFile("beforeSortData.txt");//归并排序
}

int main()
{
	f0();//生成随机数文件
	f1();//文件归并
	return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

wsl2中kali linux下的docker使用教程（教程总结）

wsl2中kali linux下的docker使用教程（教程总结）

一、前言 上一篇关于kali linux的文章是图形界面的配置&#xff0c;这里作者准备补充两点&#xff0c;一点是在使用VNC时&#xff0c;如果F8不能用的话&#xff0c;可以试试AltF8&#xff1b;然后就是VNC在初始化设置时的三个设置选项依次是密码、再输一次以及设置仅观看密码。…
阅读更多...
Linux系统使用valgrind分析C++程序内存资源使用情况

Linux系统使用valgrind分析C++程序内存资源使用情况

内存占用是我们开发的时候需要重点关注的一个问题&#xff0c;我们可以人工根据代码推理出一个消耗内存较大的函数&#xff0c;也可以推理出大概会消耗多少内存&#xff0c;但是这种方法不仅麻烦&#xff0c;而且得到的只是推理的数据&#xff0c;而不是实际的数据。 我们可以…
阅读更多...
【通俗理解】ELBO（证据下界）——机器学习中的“情感纽带”

【通俗理解】ELBO（证据下界）——机器学习中的“情感纽带”

【通俗理解】ELBO&#xff08;证据下界&#xff09;——机器学习中的“情感纽带” 关键词提炼 #ELBO #证据下界 #变分推断 #机器学习 #潜变量模型 #KL散度 #期望 #对数似然 第一节&#xff1a;ELBO的类比与核心概念【尽可能通俗】 ELBO&#xff0c;即证据下界&#xff0c;在…
阅读更多...
【pyspark学习从入门到精通14】MLlib_1

【pyspark学习从入门到精通14】MLlib_1

目录 包的概览 加载和转换数据 在前文中&#xff0c;我们学习了如何为建模准备数据。在本文中&#xff0c;我们将实际使用这些知识&#xff0c;使用 PySpark 的 MLlib 包构建一个分类模型。 MLlib 代表机器学习库。尽管 MLlib 现在处于维护模式&#xff0c;即它不再积极开发…
阅读更多...
业务架构、数据架构、应用架构和技术架构

业务架构、数据架构、应用架构和技术架构

TOGAF(The Open Group Architecture Framework)是一个广泛应用的企业架构框架&#xff0c;旨在帮助组织高效地进行架构设计和管理。 TOGAF 的核心就是由我们熟知的四大架构领域组成:业务架构、数据架构、应用架构和技术架构。 企业数字化架构设计中的最常见要素是4A 架构。 4…
阅读更多...
阿里巴巴官方「SpringCloudAlibaba全彩学习手册」限时开源！

阿里巴巴官方「SpringCloudAlibaba全彩学习手册」限时开源！

最近我在知乎上看过的一个热门回答&#xff1a; 初级 Java 开发面临的最大瓶颈在于&#xff0c;脱离不出自身业务带来的局限。日常工作中大部分时间在增删改查、写写接口、改改 bug&#xff0c;久而久之就会发现&#xff0c;自己的技术水平跟刚工作时相比没什么进步。 所以我们…
阅读更多...
后端数据增删改查基于Springboot+mybatis mysql 时间根据当时时间自动填充，数据库连接查询不一致，mysql数据库连接不好用

后端数据增删改查基于Springboot+mybatis mysql 时间根据当时时间自动填充，数据库连接查询不一致，mysql数据库连接不好用

目录 后端数据增删改查Springboot 实体&#xff08;entity&#xff09;类引进添加UserMapper接口 创建对用的UserController注意数据库查询不一致新增数据更新删除postman测试 后端数据增删改查 基于之前构建系统&#xff0c;实现用户数据的CRUD。 打开navicat16&#xff0c;…
阅读更多...
堆外内存泄露排查经历

堆外内存泄露排查经历

优质博文&#xff1a;IT-BLOG-CN 一、问题描述 淘宝后台应用从今年某个时间开始docker oom的量突然变多&#xff0c;确定为堆外内存泄露。 后面继续按照上一篇对外内存分析方法的进行排查(jemalloc、pmap、mallocpmap/mapsNMTjstackgdb)&#xff0c;但都没有定位到问题。至于…
阅读更多...
WebSocket详解、WebSocket入门案例

WebSocket详解、WebSocket入门案例

目录 1.1 WebSocket介绍 http协议&#xff1a; webSocket协议&#xff1a; 1.2WebSocket协议&#xff1a; 1.3客户端&#xff08;浏览器&#xff09;实现 1.3.2 WebSocket对象的相关事宜&#xff1a; 1.3.3 WebSOcket方法 1.4 服务端实现 服务端如何接收客户端发送的请…
阅读更多...
Vue3 源码解析（三）：静态提升

Vue3 源码解析（三）：静态提升

什么是静态提升 Vue3 尚未发布正式版本前&#xff0c;尤大在一次关于 Vue3 的分享中提及了静态提升&#xff0c;当时笔者就对这个亮点产生了好奇&#xff0c;所以在源码阅读时&#xff0c;静态提升也是笔者的一个重点阅读点。 那么什么是静态提升呢&#xff1f;当 Vue 的编译器…
阅读更多...
C++优选算法十四 优先级队列（堆）

C++优选算法十四 优先级队列（堆）

C 中的优先级队列&#xff08;Priority Queue&#xff09;是一种容器适配器&#xff0c;它提供队列的功能&#xff0c;但元素不是按照插入的顺序被访问&#xff0c;而是根据它们的优先级被访问。默认情况下&#xff0c;优先级队列是一个最大堆&#xff08;Max-Heap&#xff09;…
阅读更多...
综合练习--轮播图

综合练习--轮播图

本篇博客将教大家实现一个基础的轮播图。 源代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0&qu…
阅读更多...
“AI玩手机”原理揭秘：大模型驱动的移动端GUI智能体

“AI玩手机”原理揭秘：大模型驱动的移动端GUI智能体

作者&#xff5c;郭源 前言 在后LLM时代&#xff0c;随着大语言模型和多模态大模型技术的日益成熟&#xff0c;AI技术的实际应用及其社会价值愈发受到重视。AI智能体&#xff08;AI Agent&#xff09;技术通过集成行为规划、记忆存储、工具调用等机制&#xff0c;为大模型装上…
阅读更多...
光伏电站的智慧施工详解

光伏电站的智慧施工详解

光伏电站的智慧施工是利用先进的技术和管理方法&#xff0c;提高施工效率、质量和安全性&#xff0c;降低成本&#xff0c;实现光伏电站建设的智能化、数字化和绿色化。 下面从鹧鸪云智慧施工软件详细施工管理的步骤说起。 项目总览 包含我负责的项目、我参与的项目、我创建…
阅读更多...
django——创建 Django 项目和 APP

django——创建 Django 项目和 APP

2.创建 Django 项目和 APP 命令&#xff1a; 创建Django项目 django-admin startproject name 创建子应用 python manager.py startapp name 2.1 创建工程 在使用Flask框架时&#xff0c;项目工程目录的组织与创建是需要我们自己手动创建完成的。 在django中&#xff0c;…
阅读更多...
李春葆《数据结构》-课后习题代码题

李春葆《数据结构》-课后习题代码题

一&#xff1a;假设不带权有向图采用邻接矩阵 g 存储&#xff0c;设计实现以下功能的算法&#xff1a; &#xff08;1&#xff09;求出图中每个顶点的入度。 代码&#xff1a; void indegree(MatGraph g){int i,j,n;printf("各个顶点的入度&#xff1a;\n");for(i…
阅读更多...
wsl安装

wsl安装

一. wsl简介 1. wsl和wsl2的区别 wsl需要把linux命令翻译为windows命令&#xff0c;性能差一些。 wsl2直接使用linux内核&#xff0c;不需要翻译&#xff0c;性能好&#xff0c;但开销相对大一点&#xff0c;因为需要多运行一个hyper-v虚拟机 (并非完整的虚拟机&#xff0c;是…
阅读更多...
Java-06 深入浅出 MyBatis - 一对一模型 SqlMapConfig 与 Mapper 详细讲解测试

Java-06 深入浅出 MyBatis - 一对一模型 SqlMapConfig 与 Mapper 详细讲解测试

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 大数据篇正在更新&#xff01;https://blog.csdn.net/w776341482/category_12713819.html 目前已经更新到了&#xff1a; MyBatis&#xff…
阅读更多...
GPT中转站技术架构

GPT中转站技术架构

本文介绍阿波罗AI中转站&#xff08;https://api.ablai.top/&#xff09;的技术架构&#xff0c;该中转API的技术架构采用了分布式架构、智能调度和API中转等技术&#xff0c;确保了全球范围内的高效访问和稳定运行。以下是对该技术架构的详细分析&#xff1a; 分布式架构 分…
阅读更多...
远程服务器Docker使用本地代理加速访问外部资源

远程服务器Docker使用本地代理加速访问外部资源

Docker在pull镜像的时候非常缓慢&#xff0c;但是远程主机没有安装代理&#xff0c;就很为难&#xff0c;现在分享一个可以让远程服务器使用本地代理加速的方法 配置Docker代理 新建文件夹 mkdir -p /etc/systemd/system/docker.service.d 切换到这个文件夹里 cd /etc/system…
阅读更多...
最新文章

Copyright @ 2022~2023