17 外排序

排序分为内排序和外排序,内排序是在内存中的排序。外排序指在磁盘中文件的排序,因为在磁盘中,不能进行下标访问,归并排序经常用于磁盘中文件的排序

假如有10亿个整形数据在磁盘中,要对它排序,内存中只有1G空间,10亿需要4G。可以将这个文件划分成好几块1G大小的排序,再对这些1G文件两两归并,得到4G的排序后文件

在这里插入图片描述

方便演示外排序,手动生成100的数据量,命名为data.txt文件每10个数据读到内存中一排序,可以用快速排序,排完序写到新文件,sub+编号.txt,不断循环对这些小文件归并汇总并生成新文件
在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

//三数取中
int GetIndex(int ary[], int left, int right)
{
	//int mid = (left + right) / 2;
	int mid = left + rand() % (right - left);

	if (ary[mid] > ary[left])
	{
		if (ary[mid] < ary[right])
		{
			return mid;
		}
		else if (ary[left] > ary[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	//ary[mid] < ary[left]
	else
	{
		if (ary[mid] > ary[right])
		{
			return mid;
		}
		else if (ary[left] > ary[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
}

int QSplit(int ary[], int left, int right)
{
	//三数取中
	int mid = GetIndex(ary, left, right);
	Swap(&ary[left], &ary[mid]);

	int keyi = left;
	while (left < right)
	{
		//右边找小
		while (left < right && ary[right] >= ary[keyi])
		{
			right--;
		}
		//左边找大
		while (left < right && ary[left] <= ary[keyi])
		{
			left++;
		}

		Swap(&ary[left], &ary[right]);
	}

	Swap(&ary[left], &ary[keyi]);

	return left;
}

//升序排列 区间[left,right]
void Qsort(int ary[], int left, int right)
{
	//区间错误,返回
	if (left >= right)
	{
		return;
	}


	int keyi = QSplit(ary, left, right);
	//递归左右区间,keyi处除外
	Qsort(ary, left, keyi - 1);
	Qsort(ary, keyi + 1, right);

}

void MergeFile(const char* file1, const char* file2, const char* mfile)
{
	FILE* fout1;
	fout1 = fopen(file1, "r");

	FILE* fout2;
	fout2 = fopen(file2, "r");

	FILE* fin;
	fin = fopen(mfile, "w");

	int num1 = 0;
	int num2 = 0;
	int ret1 = fscanf(fout1, "%d", &num1);
	int ret2 = fscanf(fout2, "%d", &num2);

	while (ret1 != EOF && ret2 != EOF)
	{
		if (num1 <= num2)
		{
			fprintf(fin, "%d\n", num1);
			ret1 = fscanf(fout1, "%d", &num1);
		}
		else
		{
			fprintf(fin, "%d\n", num2);
			ret2 = fscanf(fout2, "%d", &num2);
		}
	}

	
	while (ret1 != EOF)
	{
		fprintf(fin, "%d\n", num1);
		ret1 = fscanf(fout1, "%d", &num1);
	}

	while (ret2 != EOF)
	{
		fprintf(fin, "%d\n", num2);
		ret2 = fscanf(fout2, "%d", &num2);

	}
	fclose(fout1);
	fclose(fout2);
	fclose(fin);
}

int main()
{
	FILE* fdata;
	fdata = fopen("data.txt", "r");

	//分割一段段数据,内存排序写到小文件
	int ary[10];
	int n = 10; //每10个排序
	int num = 0; //临时读取内容
	char subfile[20]; //小文件名字
	int filei = 1;  //小文件编号
	int i = 0;

	while (fscanf(fdata, "%d", &num) != EOF)
	{
		if (i < n)
		{
			ary[i++] = num;
		}
		//排序
		if (i == 10)
		{
			Qsort(ary, 0, n - 1);
			sprintf(subfile, "sub%d.txt", filei++);
			FILE* fsub;
			fsub = fopen(subfile, "w");

			for (int i = 0; i < n; i++)
			{
				fprintf(fsub, "%d\n", ary[i]);
			}
			fclose(fsub);

			i = 0;
		}
		
	}

	//互相归并到文件,实现整体有序
	char file1[100] = "sub1.txt";
	char file2[100] = "sub2.txt";
	char mfile[100] = "merge.txt";

	for (int i = 2; i <= filei - 1; i++)
	{
		//读取file1和file2,归并出mfile
		MergeFile(file1, file2, mfile);

		remove(file1);
		remove(file2);

		strcpy(file1, mfile);
		sprintf(file2, "sub%d.txt", i + 1);
		sprintf(mfile, "merge%d.txt",i + 1);
	}
	printf("hello world\r\n");
	return 0;
}


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

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

相关文章

水果FL Studio21.2最新中文版功能特点介绍

FL Studio 21的特点和优势包括&#xff1a; 丰富的主题换肤&#xff1a;用户可以通过调整色调、饱和度、亮度、文本、仪表和步进序列器的颜色&#xff0c;来个性化定制FL Studio 21的外观&#xff0c;使其更符合个人审美或工作风格。更快的音频编辑&#xff1a;FL Studio 21集…

AI少女/HS2甜心选择2 仿剑三剑灵人物卡全合集打包

AI少女/HS2甜心选择2 仿剑三剑灵人物卡全合集打包 内含&#xff1a;菩提禅音[剑网3]明教晓天喵姐[剑3]明教晓天喵姐无帽版[剑3]茱莉亚[剑灵] 下载地址&#xff1a; https://www.changyouzuhao.cn/12492.html

软件价值12-射箭游戏

射箭游戏&#xff0c;按空格键发射&#xff0c;打击移动靶&#xff0c;左上角显示成绩状态。 代码&#xff1a; import pygame import sys import random# 初始化Pygame pygame.init()# 设置窗口大小 SCREEN_WIDTH 800 SCREEN_HEIGHT 600 screen pygame.display.set_mode((…

【开源】基于JAVA+Vue+SpringBoot的就医保险管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 科室档案模块2.2 医生档案模块2.3 预约挂号模块2.4 我的挂号模块 三、系统展示四、核心代码4.1 用户查询全部医生4.2 新增医生4.3 查询科室4.4 新增号源4.5 预约号源 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVue…

DS:树及二叉树的相关概念

创作不易&#xff0c;兄弟们来波三连吧&#xff01;&#xff01; 一、树的概念及结构 1.1 树的概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树&#xff0c…

利用Cloudflare Workers实现网页状态监控

首先 Fork cf-workers-status-page 浏览器地址栏输入 https://deploy.workers.cloudflare.com/?urlhttps://github.com/$YourUserName/cf-workers-status-page 获取 Cloudflare 账户内的 Account ID 和 API Token 授权的 token 需要 workes 的编辑权限 在 Github actio…

LeetCode二叉树的垂序遍历

题目描述 给你二叉树的根结点 root &#xff0c;请你设计算法计算二叉树的 垂序遍历 序列。 对位于 (row, col) 的每个结点而言&#xff0c;其左右子结点分别位于 (row 1, col - 1) 和 (row 1, col 1) 。树的根结点位于 (0, 0) 。 二叉树的 垂序遍历 从最左边的列开始直到…

DolphinScheduler安装与配置

DolphinScheduler概述 Apache DolphinScheduler是一个分布式、易扩展的可视化DAG工作流任务调度平台。致力于解决数据处理流程中错综复杂的依赖关系&#xff0c;使调度系统在数据处理流程中开箱即用。 DolphinScheduler的主要角色如下&#xff1a; MasterServer采用分布式无…

CPython:表达式的求值顺序(evaluation order)

相关阅读 Pythonhttps://blog.csdn.net/weixin_45791458/category_12403403.html?spm1001.2014.3001.5482 C中表达式的求值 C语言针对表达式的计算&#xff0c;设置了操作符的优先级和结合性这两个特性&#xff0c;优先级用于解析不同优先级的符号&#xff0c;结合性用于解析…

【基础】第K大与第K小数

说明 给定一个长度为N(0< n< 10000)的序列&#xff0c;保证每一个序列中的数字a[i]是正整数 &#xff0c;编程要求求出整个序列中第k大的数字减去第k小的数字的值m&#xff0c;并判断m是否为质数。(0< k< n) 输入数据 第一行为2个数n&#xff0c;k&#xff08;…

【北邮鲁鹏老师计算机视觉课程笔记】10 Classification 分类

【北邮鲁鹏老师计算机视觉课程笔记】10 Classification 分类 1 图像识别的基本范式 检测问题&#xff1a;不仅要知道有没有&#xff0c;还要知道在哪里 分类是整图级标签&#xff0c;检测是区域级标签&#xff0c;分割是像素级标签 2 检测任务的应用 3 单实例识别与类别识别…

《Linux 简易速速上手小册》第3章: 文件系统与权限(2024 最新版)

文章目录 3.1 Linux 文件系统结构3.1.1 重点基础知识3.1.2 重点案例&#xff1a;设置一个 Web 服务器3.1.3 拓展案例 1&#xff1a;日志文件分析3.1.3 拓展案例 2&#xff1a;备份用户数据 3.2 理解文件权限3.2.1 重点基础知识3.2.2 重点案例&#xff1a;共享项目文件夹3.2.3 拓…

java学习08---面向对象

一 类和对象 1 类和对象的理解 客观存在的事物皆为对象 &#xff0c;所以我们也常常说万物皆对象。 类 简单理解&#xff1a;类就是对现实事物的一种描述 类是对象的数据类型&#xff0c;类是具有相同属性和行为的一组对象的集合 类是对现实生活中一类具有共同属性和行为的事…

Python教程56:海龟画图turtle画kitty猫

---------------turtle源码集合--------------- Python教程91&#xff1a;关于海龟画图&#xff0c;Turtle模块需要学习的知识点 Python教程51&#xff1a;海龟画图turtle画&#xff08;三角形、正方形、五边形、六边形、圆、同心圆、边切圆&#xff0c;五角星&#xff0c;椭…

【python量化交易】qteasy使用教程02 - 获取和管理金融数据

qteasy教程2 - 获取并管理金融数据 qteasy教程2 - 获取并管理金融数据开始前的准备工作获取基础数据以及价格数据下载交易日历和基础数据查看股票和指数的基础数据下载沪市股票数据从本地获取股价数据生成K线图 数据类型的查找定期下载数据到本地回顾总结 qteasy教程2 - 获取并…

【Web】CVE-2021-31805 s2-062漏洞复现学习

目录 Struts2介绍 漏洞概况 OGNL与Struts2 简单原理 漏洞复现 正向rce 反弹shell payload分析 Struts2介绍 Struts 2 是一个流行的用于构建 Java Web 应用程序的开源 Web 应用程序框架。它是 Apache 软件基金会下的一个顶级项目&#xff0c;是 Struts 框架的升级版本。…

docker磁盘不足!已解决~

目录 &#x1f35f;1.查看docker镜像目录 &#x1f9c2;2.停止docker服务 &#x1f953;3.创建新的目录 &#x1f32d;4.迁移目录 &#x1f37f;5.编辑迁移的目录 &#x1f95e;6.重新加载docker &#x1f354;7.检擦docker新目录 &#x1f373;8.删掉旧目录 1.查看doc…

衍生式设计之随机删除Revit幕墙网格

上次教程&#xff0c;我们创建了一个随机的三角形&#xff08;一个小例子&#xff0c;告诉你什么是衍生式设计&#xff09;&#xff0c;用来给大家简单介绍了下啥是衍生式设计&#xff0c;但是三角形是在Dynamo里做的&#xff0c;似乎和Revit没啥关系&#xff0c;那么本次呢&am…

【树莓派系统的位数】

要区分 ARM 架构下载的版本是 32 位还是 64 位&#xff0c;可以执行以下步骤&#xff1a; 执行以下命令来检查 Raspberry Pi 的 CPU 类型&#xff1a; uname -m如果返回的结果是 aarch64&#xff0c;则表示您的 Raspberry Pi 是 64 位的 ARM 架构。如果返回的结果是 armv7l&a…

Linux_文件系统

假定外部存储设备为磁盘&#xff0c;文件如果没有被使用&#xff0c;那么它静静躺在磁盘上&#xff0c;如果它被使用&#xff0c;则文件将被加载进内存中。故此&#xff0c;可以将文件分为内存文件和磁盘文件。 内存文件 磁盘文件 软、硬链接 一.内存文件 1.1 c语言的文件接口 …