当前位置: 首页 > news >正文

【数据结构】外部排序、多路平衡归并与败者树、置换-选择排序(生成初始归并段)、最佳归并树算法

  目录

1、外部排序

        1.1 基本概念

        1.2 方法 

2、多路平衡归并与败者树

        2.1 K路平衡归并

        2.2 败者树 

3、置换-选择排序(生成初始归并段)​编辑

4、最佳归并树

        4.1 理论基础​编辑

        4.2 构造方法 ​编辑

5、各种排序算法的性质


1、外部排序

1.1 基本概念

        外部排序是指对大规模数据进行排序,其中无法将整个数据集一次性加载到内存中。因此需要将数据划分为适当大小的块,然后对每个块进行排序。在此之后,将这些排好序的块合并成更大的块,直到最终得到一个已排序的数据集。

        外部排序是一种常见的数据处理技术,适用于需要对大量数据进行排序的场景,例如处理大型数据库或处理大型文件。通常采用归并排序算法来实现外部排序,其核心思想是将多个有序的子序列合并成一个有序的序列,以减少排序的时间和空间复杂度。

        在外部排序中,需要考虑如何对数据进行分块、如何将块排序以及如何将排好序的块进行合并。为了提高排序效率,还需要考虑如何优化输入和输出数据的读取和写入。

1.2 方法 

外部排序是一种处理超过内存容量的数据的排序方法。以下是外部排序的几种常见方法:

  1. 归并排序:将大文件分成若干个小文件,排序这些小文件,再进行归并排序,将小文件合并成一个有序的大文件。

  2. 快速排序:将大文件分割成若干个小文件,对这些小文件进行快速排序,然后将排序好的小文件合并成一个有序的大文件。

  3. 堆排序:利用堆的结构对数据进行排序,可以将大文件分成若干个小文件,将小文件中的数据建成堆,然后再进行堆排序。

  4. 多路归并排序:将大文件划分成多个子文件,每个子文件都小于内存容量,然后对于每个子文件,将其分成多个块,将每个块读入内存进行排序,最后进行多路归并。

  5. 分块排序:将大文件划分为若干个块,每个块都可以在内存中排序,然后将每个块中的数据合并成一个有序的文件。

        这些方法都可以通过将大文件分割成小文件或块来解决内存容量不足的问题,并利用多路归并等技术来进行排序。

例子:

        假设我们有一个文件,其中包含 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应用程序中的弹出窗口每次都显示在屏幕的中央&#xff0c;您可以使用以下方法&#xff1a; 使用QMessageBox的move方法手动设置窗口位置&#xff1a; #include <QApplication> #include <QMessageBox> #include <QDesk…...

正点原子嵌入式linux驱动开发——STM32MP1启动详解

STM32单片机是直接将程序下载到内部 Flash中&#xff0c;上电以后直接运行内部 Flash中的程序。 STM32MP157内部没有供用户使用的 Flash&#xff0c;系统都是存放在外部 Flash里面的&#xff0c;比如 EMMC、NAND等&#xff0c;因此 STM32MP157上电以后需要从外部 Flash加载程序…...

FPGA的数字钟带校时闹钟报时功能VHDL

名称&#xff1a;基于FPGA的数字钟具有校时闹钟报时功能 软件&#xff1a;Quartus 语言&#xff1a;VHDL 要求&#xff1a; 1、计时功能:这是数字钟设计的基本功能&#xff0c;每秒钟更新一次,并且能在显示屏上显示当前的时间。 2、闹钟功能:如果当前的时间与闹钟设置的时…...

分析各种表达式求值过程

目录 算术运算与赋值 编译器常用的两种优化方案 常量传播 常量折叠 加法 Debug编译选项组下编译后的汇编代码分析 Release开启02执行效率优先 减法 Release版下优化和加法一致&#xff0c;不再赘述 乘法 除法 算术结果溢出 自增和自减 关系运算与逻辑运算 JCC指…...

企业风险管理策略终极指南

企业风险管理不一定是可怕的。企业风险管理是一个模糊且难以定义的主题领域。它涵盖了企业的多种风险和程序&#xff0c;与传统的风险管理有很大不同。 那么&#xff0c;企业风险管理到底是什么&#xff1f;在本文中&#xff0c;我们将确定它是什么&#xff0c;提出两种常见的…...

OpenCV之分水岭算法(watershed)

Opencv 中 watershed函数原型&#xff1a; void watershed( InputArray image, InputOutputArray markers ); 第一个参数 image&#xff0c;必须是一个8bit 3通道彩色图像矩阵序列&#xff0c;第一个参数没什么要说的。关键是第二个参数 markers&#xff0c;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&#xff1a;opencv find 不到 在 CMakeLists 中将正确的 OpenCV库 路径添加到 CMAKE_PREFIX_PATH 变量中 set(CMAKE_PREFIX_PATH “/mnt/usr/local” ${CMAKE_PREFIX_PATH}) 问题2&#xff1a; rknn_api.h 找不到 将该文件从别处复制到项目 include 文件夹 问题3&…...

[vue-admin-template实战笔记]

1.克隆项目 git clone gitgitee.com:panjiachen/vue-admin-template.git 2.安装依赖 npm install 3.运行项目就会自动打开网页&#xff0c;并且热部署插件 npm run dev 4.查看代码 //将vue-admin-template拖入到idea中即可查看代码 1)并且发现&#xff0c;常用的东西已经集…...

unity 限制 相机移动 区域(无需碰撞检测)

限制功能原著地址&#xff1a;unity限制相机可移动区域&#xff08;box collider&#xff09;_unity限制相机移动区域_manson-liao的博客-CSDN博客 一、创建限制区域 创建一个Cube&#xff0c;Scale大小1&#xff0c;添加组件&#xff1a;BoxCollder&#xff0c;调整BoxColld…...

Hudi第二章:集成Spark

系列文章目录 Hudi第一章&#xff1a;编译安装 Hudi第二章&#xff1a;集成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 区域&#xff0c;既MVVM中的View <div id"app">{{ message }} </div…...

docker-compose内网本地安装

1&#xff1a;通过包管理器安装 Docker Compose&#xff0c;请按照以下步骤进行操作&#xff1a; 首先&#xff0c;确保你的系统上已经安装了 Docker。如果尚未安装 Docker&#xff0c;请根据你的操作系统使用适当的包管理器进行安装打开终端&#xff0c;并运行以下命令下载 D…...

ThreeJs的场景实现鼠标拖动旋转控制

前面一个章节中已经实现在场景中放置一个正方体&#xff0c;并添加灯光使得正方体可见。但是由于是静态的还不能证明是3D的&#xff0c;我们需要添加一些控制器&#xff0c;使得通过鼠标控制正方体可以动起来&#xff0c;实现真正的3D效果&#xff0c;由此引入OrbitControls组件…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...