【数据结构】外部排序、多路平衡归并与败者树、置换-选择排序(生成初始归并段)、最佳归并树算法
目录
1、外部排序
1.1 基本概念
1.2 方法
2、多路平衡归并与败者树
2.1 K路平衡归并
2.2 败者树
3、置换-选择排序(生成初始归并段)编辑
4、最佳归并树
4.1 理论基础编辑
4.2 构造方法 编辑
5、各种排序算法的性质
1、外部排序
1.1 基本概念
外部排序是指对大规模数据进行排序,其中无法将整个数据集一次性加载到内存中。因此需要将数据划分为适当大小的块,然后对每个块进行排序。在此之后,将这些排好序的块合并成更大的块,直到最终得到一个已排序的数据集。
外部排序是一种常见的数据处理技术,适用于需要对大量数据进行排序的场景,例如处理大型数据库或处理大型文件。通常采用归并排序算法来实现外部排序,其核心思想是将多个有序的子序列合并成一个有序的序列,以减少排序的时间和空间复杂度。
在外部排序中,需要考虑如何对数据进行分块、如何将块排序以及如何将排好序的块进行合并。为了提高排序效率,还需要考虑如何优化输入和输出数据的读取和写入。
1.2 方法
外部排序是一种处理超过内存容量的数据的排序方法。以下是外部排序的几种常见方法:
-
归并排序:将大文件分成若干个小文件,排序这些小文件,再进行归并排序,将小文件合并成一个有序的大文件。
-
快速排序:将大文件分割成若干个小文件,对这些小文件进行快速排序,然后将排序好的小文件合并成一个有序的大文件。
-
堆排序:利用堆的结构对数据进行排序,可以将大文件分成若干个小文件,将小文件中的数据建成堆,然后再进行堆排序。
-
多路归并排序:将大文件划分成多个子文件,每个子文件都小于内存容量,然后对于每个子文件,将其分成多个块,将每个块读入内存进行排序,最后进行多路归并。
-
分块排序:将大文件划分为若干个块,每个块都可以在内存中排序,然后将每个块中的数据合并成一个有序的文件。
这些方法都可以通过将大文件分割成小文件或块来解决内存容量不足的问题,并利用多路归并等技术来进行排序。
例子:
假设我们有一个文件,其中包含 1000 万个整数,需要对其进行排序。然而,计算机的内存只能容纳 1000 个整数,因此我们需要将该文件分成 10000 个大小为 1000 的块。
接下来,我们将这些块读取到内存中,对每个块进行排序,然后将它们写回磁盘。这是称为"归并排序"的过程。在每个块中进行排序的好处是可以优化内存中的使用,而且在每个块中进行的排序比在整个文件上进行的排序更快。
接下来,我们将排好序的 10000 个块合并成一个大的有序文件。为了合并这些块,我们可以使用归并排序的原理。我们将前两个块合并成一个块,再将第三个块与已合并的块合并,以此类推,直到所有块都被合并成一个大块。
最后,我们将这个大块写回磁盘,即得到了完全排好序的文件。这个过程可能会涉及到多次读取和写入磁盘,但是外部排序的好处是可以处理非常大的文件,而不需要太多的内存。
2、多路平衡归并与败者树
2.1 K路平衡归并
K路平衡归并是一种归并排序的变体,它将一个大文件分成K个子文件并对每个子文件进行排序,然后将它们合并成一个大文件。它的主要目的是在内存有限的情况下对大型数据集进行排序。
K路平衡归并的基本思想是将输入文件分成K份,每份放入磁盘上的一个块中,然后针对每个块进行排序。排序后,每个块中的第一个元素被放入一个最小堆或多个最小堆中,堆的大小为K。从堆中选择最小元素,将其放入输出缓冲区中,并且从所属块的下一个元素中选择一个元素来取代刚刚被放入输出缓冲区的元素。重复此过程,直到所有输入文件中的元素都被放入输出缓冲区中。输出缓冲区的元素可以按顺序写入输出文件。
K路平衡归并的时间复杂度为O(n log n),其中n表示输入文件的大小。它需要的额外空间取决于K和块的大小,通常情况下可以控制在几兆字节的范围内。
2.2 败者树
败者树是一种用于外部排序的数据结构,它基于树形结构,常用于对大量数据进行排序,尤其是当内存无法容纳所有待排序数据时。败者树的思想在于通过比较已排序的子序列中最小的元素来确定最终的排序顺序。
在败者树中,首先构建一棵初始的完全二叉树,其中每个节点存储一个元素。初始时,将每个需要排序的子序列的第一个元素放入这棵二叉树的最底层叶子节点。接下来,从叶子节点开始向上进行比较,每次比较两个叶子节点中的较小值,并将较小值向其父节点传递。这样,最终得到的顶部节点就是已排序的所有元素中的最小值。
在外部排序中,每次从磁盘中读取一定数量的数据块并进行排序,然后将每个数据块的最小值放入败者树中,以确定整体排序的顺序。当一个数据块中的所有元素都已被取出并放入败者树中时,将从该数据块中读取下一个元素,直到整个排序过程结束。
败者树的主要优点是它只需要常数级别的额外内存空间,并且可以对任意大小的数据集进行排序。它的主要缺点在于实现比较复杂,需要一定的算法知识和技巧。
3、置换-选择排序(生成初始归并段)
4、最佳归并树
4.1 理论基础
4.2 构造方法
5、各种排序算法的性质
1. 冒泡排序:稳定,平均时间复杂度O(n^2);
2. 选择排序:不稳定,平均时间复杂度O(n^2);
3. 插入排序:稳定,平均时间复杂度O(n^2);
4. 快速排序:不稳定,平均时间复杂度O(nlogn);
5. 归并排序:稳定,平均时间复杂度O(nlogn);
6. 堆排序:不稳定,平均时间复杂度O(nlogn);
7. 希尔排序:不稳定,平均时间复杂度O(nlogn);
8. 基数排序:稳定,平均时间复杂度O(d(n+k)),其中d是数字的最大位数。
稳定性指的是排序后相同元素之间的相对位置是否改变;时间复杂度指的是排序算法在最坏情况下的时间复杂度。
相关文章:
【数据结构】外部排序、多路平衡归并与败者树、置换-选择排序(生成初始归并段)、最佳归并树算法
目录 1、外部排序 1.1 基本概念 1.2 方法 2、多路平衡归并与败者树 2.1 K路平衡归并 2.2 败者树 3、置换-选择排序(生成初始归并段)编辑 4、最佳归并树 4.1 理论基础编辑 4.2 构造方法 编辑 5、各种排序算法的性质 1、外部排序 1.1 基本概…...
抽象工厂模式 创建性模式之五
在看这篇文章之前,请先看看“简单工厂模式”和“工厂方法模式”这两篇博文,会更有助于理解。我们现在已经知道,简单工厂模式就是用一个简单工厂去创建多个产品,工厂方法模式是每一个具体的工厂只生产一个具体的产品,然…...
servlet如何获取PUT和DELETE请求的参数
1. servlet为何不能获取PUT和DELETE请求的参数 Servlet的规范是POST的数据需要转给request.getParameter*()方法,没有规定PUT和DELETE请求也这么做 The Servlet spec requires form data to be available for HTTP POST but not for HTTP PUT or PATCH requests. T…...
【Vue.js】使用Element中的Mock.js搭建首页导航左侧菜单---【超高级教学】
一,Mock.js 1.1 认识Mock.js Mock.js是一个用于前端开发中生成随机数据、模拟接口响应的 JavaScript 库。模拟数据的生成器,用来帮助前端调试开发、进行前后端的原型分离以及用来提高自动化测试效率 总结来说,Element中的Mock.js是一个用于…...
从技术创新到应用实践,百度智能云发起大模型平台应用开发挑战赛!
大模型已经成为未来技术发展方向的重大变革,热度之下更需去虚向实,让技术走进产业场景。在这样的背景下,百度智能云于近期发起了“百度智能云千帆大模型平台应用开发挑战赛”。 挖掘大模型落地应用 千帆大模型平台应用开发挑战赛启动 在不久前…...
简单三步 用GPT-4和Gamma自动生成PPT PDF
1. 用GPT-4 生产PPT内容 我想把下面的文章做成PPT,请你给出详细的大纲和内容 用于谋生的知识,学生主要工作是学习,成年人的工作是养家糊口,这是基本的要求,在这之上,才能有更高的追求。 不要短期期望过高…...
QT设置弹窗显示屏幕中央
Qt设置每次运行弹窗显示屏幕中央 要确保Qt应用程序中的弹出窗口每次都显示在屏幕的中央,您可以使用以下方法: 使用QMessageBox的move方法手动设置窗口位置: #include <QApplication> #include <QMessageBox> #include <QDesk…...
正点原子嵌入式linux驱动开发——STM32MP1启动详解
STM32单片机是直接将程序下载到内部 Flash中,上电以后直接运行内部 Flash中的程序。 STM32MP157内部没有供用户使用的 Flash,系统都是存放在外部 Flash里面的,比如 EMMC、NAND等,因此 STM32MP157上电以后需要从外部 Flash加载程序…...
FPGA的数字钟带校时闹钟报时功能VHDL
名称:基于FPGA的数字钟具有校时闹钟报时功能 软件:Quartus 语言:VHDL 要求: 1、计时功能:这是数字钟设计的基本功能,每秒钟更新一次,并且能在显示屏上显示当前的时间。 2、闹钟功能:如果当前的时间与闹钟设置的时…...
分析各种表达式求值过程
目录 算术运算与赋值 编译器常用的两种优化方案 常量传播 常量折叠 加法 Debug编译选项组下编译后的汇编代码分析 Release开启02执行效率优先 减法 Release版下优化和加法一致,不再赘述 乘法 除法 算术结果溢出 自增和自减 关系运算与逻辑运算 JCC指…...
企业风险管理策略终极指南
企业风险管理不一定是可怕的。企业风险管理是一个模糊且难以定义的主题领域。它涵盖了企业的多种风险和程序,与传统的风险管理有很大不同。 那么,企业风险管理到底是什么?在本文中,我们将确定它是什么,提出两种常见的…...
OpenCV之分水岭算法(watershed)
Opencv 中 watershed函数原型: void watershed( InputArray image, InputOutputArray markers ); 第一个参数 image,必须是一个8bit 3通道彩色图像矩阵序列,第一个参数没什么要说的。关键是第二个参数 markers,Opencv官方文档的说…...
npm 命令
目录 初始化 搜索 安装 删除 更新 换源 查看 其他 补充 1.初始化 npm init #初始化一个package.json文件 npm init -y | npm init --yes 2.搜索 npm s jquery | npm search jquery 3.安装 npm install npm -g #更新到最新版本 npm i uniq | npm ins…...
【bug 记录】yolov5_C_demo 部署在 rv1126
问题1:opencv find 不到 在 CMakeLists 中将正确的 OpenCV库 路径添加到 CMAKE_PREFIX_PATH 变量中 set(CMAKE_PREFIX_PATH “/mnt/usr/local” ${CMAKE_PREFIX_PATH}) 问题2: rknn_api.h 找不到 将该文件从别处复制到项目 include 文件夹 问题3&…...
[vue-admin-template实战笔记]
1.克隆项目 git clone gitgitee.com:panjiachen/vue-admin-template.git 2.安装依赖 npm install 3.运行项目就会自动打开网页,并且热部署插件 npm run dev 4.查看代码 //将vue-admin-template拖入到idea中即可查看代码 1)并且发现,常用的东西已经集…...
unity 限制 相机移动 区域(无需碰撞检测)
限制功能原著地址:unity限制相机可移动区域(box collider)_unity限制相机移动区域_manson-liao的博客-CSDN博客 一、创建限制区域 创建一个Cube,Scale大小1,添加组件:BoxCollder,调整BoxColld…...
Hudi第二章:集成Spark
系列文章目录 Hudi第一章:编译安装 Hudi第二章:集成Spark 文章目录 系列文章目录前言一、安装Spark1、安装Spark2.安装hive 二、spark-shell1.启动命令2.插入数据3.查询数据1.转换DF2.查询 3.更新4.时间旅行5.增量查询6.指定时间点查询7.删除数据1.获取…...
springboot和vue:八、vue快速入门
vue快速入门 新建一个html文件 导入 vue.js 的 script 脚本文件 <script src"https://unpkg.com/vuenext"></script>在页面中声明一个将要被 vue 所控制的 DOM 区域,既MVVM中的View <div id"app">{{ message }} </div…...
docker-compose内网本地安装
1:通过包管理器安装 Docker Compose,请按照以下步骤进行操作: 首先,确保你的系统上已经安装了 Docker。如果尚未安装 Docker,请根据你的操作系统使用适当的包管理器进行安装打开终端,并运行以下命令下载 D…...
ThreeJs的场景实现鼠标拖动旋转控制
前面一个章节中已经实现在场景中放置一个正方体,并添加灯光使得正方体可见。但是由于是静态的还不能证明是3D的,我们需要添加一些控制器,使得通过鼠标控制正方体可以动起来,实现真正的3D效果,由此引入OrbitControls组件…...
jdk 管理工具比对 jEnv jabba SDKMAN
jEnv、jabba、SDKMAN 这三个 JDK 管理工具进行的比对: jEnv: 地址:https://github.com/jenv/jenv 作者:Gildas Cuisinier 最后更新时间:2021年5月26日 开发语言:Shell Jabba: 地址࿱…...
华为云云耀云服务器L实例评测|部署在线图表和流程图绘制工具drawio
华为云云耀云服务器L实例评测|部署在线图表和流程图绘制工具drawio 一、云耀云服务器L实例介绍1.1 云服务器介绍1.2 优势及其应用场景1.3 支持镜像 二、云耀云服务器L实例配置2.1 重置密码2.2 服务器连接2.3 安全组配置 三、部署 drawio3.1 drawio 介绍3.2 Docker 环…...
elementui引入弹出框报错:this.$alert is not defined 解决方案
1.按需引入文件element.js 注意:引入Message,MessageBox两个组件就行,alert包括在MessageBox里面了。 之前我引入了Alert组件,发现不行 2.在vue的prototype里注册伪名字 3.组件里直接调用就行了 4.实现效果 我发现elementui调用…...
docker的组件和资源管理
Docker是一种开源的容器化平台,它提供了一种轻量级、可移植和可扩展的方式来打包、部署和运行应用程序。Docker的构成包括以下几个关键组件: Docker Engine:Docker Engine是Docker的核心组件,它负责管理容器的生命周期和资源隔离…...
SEO的优化教程(百度SEO的介绍和优化)
百度SEO关键字介绍: 百度SEO关键字是指用户在搜索引擎上输入的词语,是搜索引擎了解网站内容和相关性的重要因素。百度SEO关键字可以分为短尾词、中尾词和长尾词,其中长尾词更具有针对性和精准性,更易于获得高质量的流量。蘑菇号-…...
Tomcat以及UDP
一、Tomcat 服务端 自定义 S Tomcat服务器 S :Java后台开发 客户端 自定义 C 浏览器 B 认识一些常用的目录: bin:存放开始和结束的程序 conf:配置文件 lib:组成包 logs:输出日志 webapps&#x…...
NLP 04(GRU)
一、GRU GRU (Gated Recurrent Unit)也称门控循环单元结构,它也是传统RNN的变体,同LSTM一样能够有效捕捉长序列之间的语义关联, 缓解梯度消失或爆炸现象,同时它的结构和计算要比LSTM更简单,它的核心结构可以分为两个部分去解析: 更新门、重置门 GRU的内…...
BUUCTF reverse wp 51 - 55
findKey shift f12 找到一个flag{}字符串, 定位到关键函数, F5无效, 大概率是有花指令, 读一下汇编 这里连续push两个byte_428C54很奇怪, nop掉下面那个, 再往上找到函数入口, p设置函数入口, 再F5 LRESULT __stdcall sub_401640(HWND hWndParent, UINT Msg, WPARAM wPara…...
WebGL笔记:使用鼠标绘制多个线条应用及绘制动感线性星座
使用鼠标绘制多个线条 多个线条,肯定不是一笔画过的,而是多次画的线条既然是多线,那就需要有个容器来管理它们 1 )建立容器对象 建立一个 lineBox 对象,作为承载多边形的容器 // lineBox.js export default class …...
nodejs+vue 汽车销售系统elementui
第三章 系统分析 10 3.1需求分析 10 3.2可行性分析 10 3.2.1技术可行性:技术背景 10 3.2.2经济可行性 11 3.2.3操作可行性: 11 3.3性能分析 11 3.4系统操作流程 12 3.4.1管理员登录流程 12 3.4.2信息添加流程 12 3.4.3信息删除流程 13 第四章 系统设计与…...
莆田做网站建设/虞城seo代理地址
趁着公司不忙,抓紧充充电,开始可能会写的不好,但是每写一个都是一点进步,哈哈,加油 用js实现选项卡切换 1.获取元素 2.初始状态 3.通过循环清空元素状态 4.点击操作以及对应的内容切换 5.自定义索引(通过HT…...
企业网站建设的一般要素/百度seo排名原理
一、前言 可能大家对obproxy不是很了解,这里边我提一个类比的,mysql的mysql-router,大家应该就明白了,mysql-router是作为在mysql之上的一个"路由转发"的组件。obproxy对于oceanbase就像mysql-router之于mysql一样。 二、obpoxy是什…...
网站的运营费用吗/百度公司简介
起因: JDK的InheritableThreadLocal类可以完成父子线程值的传递。 但对于使用线程池等会缓存线程的组件的情况,线程由线程池创建好,并且线程是缓存起来反复使用的;这时父子线程关系的上下文传递已经没有意义,应用中要做…...
网站建设付款分期付款协议/电脑培训班一般多少钱
后缀为axd 的文件 - 2012-03-28 21:54其实扩展名为ashx与为axd基本上是一样的,都是用于写web handler,可以通过它来调用IHttpHandler类,它免去了普通.aspx页面的控件解析以及页面处理的过程。 唯一不同的地方是:axd扩展名的必须要…...
建筑材料价格信息网/视频号排名优化帝搜软件
1 import numpy as np2 # -*- codeing:utf-8 -*-3 __author__ youfei4 5 # 隐状态6 hidden_state [sunny, rainy]7 8 # 观测序列9 obsevition [walk, shop, clean] 10 11 12 # 根据观测序列、发射概率、状态转移矩阵、发射概率 13 # 返回最佳路径 14 def compute(…...
诚信网站体系建设工作/淘宝seo搜索排名优化
2019独角兽企业重金招聘Python工程师标准>>> JS里设定延时: 使用SetInterval和设定延时函数setTimeout 很类似。setTimeout 运用在延迟一段时间,再进行某项操作。 setTimeout("function",time) 设置一个超时对象 setInterval("…...