排序:败者树和置换选择排序(解决外部排序中的优化问题)

1.算法目的(败者树)

解决多路平衡归并带来的问题。
在外部排序中,使用k路平衡归并策略,
选出一个最小元素需要对比关键字(k-1)次,
导致内部归并所需时间增加。(可用“败者树”进行优化)

2.败者树的定义

败者树:可视为一棵完全二叉树(多了一个头头)。
k个叶结点分别是当前参加比较的元素,
非叶子结点用来记忆左右子树中的“失败者”,
而让胜者往上继续进行比较,一直到根结点。

3.败者树在多路平衡归并中的应用

在这里插入图片描述

对于k路归并,第一次构造败者,树需要对比关键字k-1次。
有了败者树,选出最小元素,只需对比关键字 「 l o g 2 k ∣ 「log_2k| log2k次。

4.败者树的实现思路

k路归并的败者树只需要定义一个长度为k的数组即可。

5.置换选择排序

可用“置换-选择排序"进一步减少初始归并段数量.
在这里插入图片描述

注:假设用于内部排序的内存工作区只能容纳3个记录。

若WA内的关键字都比MINIMAX更小,则该归并段在此截止.

使用置换-选择排序,
可以让每个初始归并段的长度超越内存工作区大小的限制.

1.步骤

设初始待排文件为FI,初始归并段输出文件为FO,内存工作区为WA,
FO和WA的初始状态为空,WA可容纳w个记录。
置换-选择算法的步骤如下:

  1. 从FI输入w个记录到工作区WA。
  2. 从WA中选出其中关键字取最小值的记录,记为MINIMAX记录。
  3. 将MINIMAX记录输出到FO中去。
  4. 若FI不空,则从FI输入下一个记录到WA中。
  5. 从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录,作为新的MINIMAX记录。
  6. 重复3~5,直至在WA中选不出新的MINIMAX记录为止,由此得到一个初始归并段,输出一个归并段的结束标志到FO中去。
  7. 重复2~6,直至WA为空。由此得到全部初始归并段。

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

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

相关文章

【C++11】多线程

多线程创建线程thread提供的成员函数获取线程id的方式线程函数参数的问题线程join场景和detach 互斥量库(mutex)mutexrecursive_mutexlock_guard 和 unique_lock 原子性操作库(atomic)条件变量库(condition_varuable&a…

一文读懂集合竞价,建议收藏,读完少交学费

集合竞价每个时间段交易规则及作用都不一样,了解集合竞价的规则,有利于琢磨主力的意图。 大部分同学都不是很关心集合竞价,也不知道如何利用集合竞价买卖股票。如上图所示,有同学在9点15看着股票涨停,立马冲进去&…

【切片】基础不扎实引发的问题

本次文章主要是来聊聊关于切片传值需要注意的问题,如果不小心,则很容易引发线上问题,如果不够理解,可能会出现奇奇怪怪的现象 问题情况: 小 A 负责一个模块功能的实现,在调试代码的时候可能不仔细&#x…

UE蓝图学习(从Unity3D而来)

一、UE组件对比Unity3D,从Unity3D过渡来学的角度出发,可以理解为在 空物体下放置子物体。UE没有U3D那种可以将组件挂在自身空物体上面。 二、UE 蓝图的情境提示,必须先找到相应的类型,对象对象、事件事件,才能找到相应…

云原生Kubernetes:Pod控制器

目录 一、理论 1.Pod控制器 2.Deployment 控制器 3.SatefulSet 控制器 4.DaemonSet 控制器 5.Job 控制器 6.CronJob 控制器 二、实验 1.Deployment 控制器 2.SatefulSet 控制器 3.DaemonSet 控制器 4.Job 控制器 5.CronJob 控制器 三、问题 1. showmount -e 报错…

QT窗口的设置、按钮的创建和对象树的概念

目录 设置窗口属性 按钮的创建 对象树 对象树的概念 构建和析构的顺序问题 设置窗口属性 在Qt官方手册中查找QWidget相关信息 或者在QT软件帮助一栏直接搜索QWidget 即可找到一些要寻找的设置属性的函数 将代码写在构造函数中 widget.cpp #include "widget.h"…

1200*A. Flipping Game(前缀和)

解析&#xff1a; 100数据量&#xff0c;两层遍历每个区间&#xff0c;然后前缀和计算1的个数&#xff0c;维护最大值即可。 #include<bits/stdc.h> using namespace std; #define int long long const int N110; int n,a[N],res,sum[N]; signed main(){scanf("%ll…

保姆级 -- Zookeeper超详解

1. Zookeeper 是什么(了解) Zookeeper 是一个 分布式协调服务 的开源框架, 主要用来解决分布式集群中应用系统的一致性问题, 例如怎样避免同时操作同一数据造成脏读的问题. ZooKeeper 本质上是 一个分布式的小文件存储系统 . 提供基于类似于文件系统的目录树方式的数据存储, …

常见的7种分布式事务解决方案(2pc,3pc,Tcc,Seta、本地事务....)

一 分布式事务 1.1 分布式事务 在分布式系统中一次操作需要由多个服务协同完成&#xff0c;这种由不同的服务之间通过网络协同完成的事务称为分布式事务。 1.首先满足事务特性&#xff1a;ACID 2.而在分布式环境下&#xff0c;会涉及到多个数据库 总结&#xff1a;分布式事务…

C运算符和控制语句

几乎每一个程序都需要进行运算&#xff0c;对数据进行加工处理&#xff0c;否则程序就没有意义了。要进行运算&#xff0c;就需规定可以使用的运算符。 C语言的运算符范围很宽&#xff0c;把除了控制语句和输人输出以外的几乎所有的基本操作都作为运算符处理。 运算符分类1 除…

Apache Flume

Flume 1.9.0 Developer Guide【Flume 1.9.0开发人员指南】 Introduction【介绍】 摘自&#xff1a;Flume 1.9.0 Developer Guide — Apache Flume Overview【概述】 Apache Flume is a distributed, reliable, and available system for efficiently collecting, aggregati…

Docker 安装Redis(集群)

3主3从redis集群配置 1、新建6个docker容器 redis 实例 docker run -d --name redis-node-1 --net host --privilegedtrue -v /data/redis/share/redis-node-1:/data redis:6.0.8 --cluster-enabled yes --appendonly yes --port 6381 docker run -d --name redis-node-2 --ne…

C理解(二):指针,数组,字符串,函数

本文主要探讨指针&#xff0c;数组&#xff0c;字符串&#xff0c;函数 指针 int *p; 未绑定:*表示p为指针变量,占4字节 int a 1;p &a; 绑定:p与a地址绑定即p中存放a的地址 *p *p 1; 解引用:p间接访问a的存储空间…

九、Delay函数

1、两个延时函数 vTaskDelay&#xff1a;至少等待指定个数的Tick Interrupt才能变为就绪态。vTaskDelayUntil&#xff1a;等待到指定的绝对时刻&#xff0c;才能变为就绪态。 2、函数原型 /* xTicksToDelay: 等待多少个Tick */ void vTaskDelay( const TickType_t xTicksToD…

Android Studio 的android.jar文件在哪儿

一般在&#xff1a;C:\Users\admin\AppData\Local\Android\Sdk\platforms\android-33下&#xff08;不一定是33&#xff0c;这个得看你Android Studio->app->builde.gradle的targetSdk是多少&#xff09; 怎么找&#xff1a; 1.打开Android Studio 粘贴地址后&#xff0…

13.(开发工具篇github)如何在GitHub上上传本地项目

一:创建GitHub账户并安装Git 二:创建一个新的仓库(repository) 三、拉取代码 git clone https://github.com/ainier-max/myboot.git git clone git@github.com:ainier-max/myboot.git四、拷贝代码到拉取后的工程 五、上传代码 (1)添加所有文件到暂存

Ci2451-2.4g无线MCU收发芯片

Ci2451 是一款集成无线收发器和8位RISC(精简指令集)MCU的SOC芯片。 无线MCU解决方案,集成丰富的MCU资源、更小尺寸,来满足设计中的各种内存、功率、尺寸要求,充分缩短2.4GHz无线产品设计周期并优化产品成本。 添加图片注释&#xff0c;不超过 140 字&#xff08;可选&#xff…

通讯网关软件016——利用CommGate X2Access实现OPC数据转储Access

本文介绍利用CommGate X2ACCESS实现从OPC Server读取数据并转储至ACCESS数据库。CommGate X2ACCESS是宁波科安网信开发的网关软件&#xff0c;软件可以登录到网信智汇(http://wangxinzhihui.com)下载。 【案例】如下图所示&#xff0c;实现从OPC Server读取数据并转储至ACCESS…

2023年【起重信号司索工(建筑特殊工种)】考试总结及起重信号司索工(建筑特殊工种)模拟考试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 起重信号司索工(建筑特殊工种)考试总结是安全生产模拟考试一点通生成的&#xff0c;起重信号司索工(建筑特殊工种)证模拟考试题库是根据起重信号司索工(建筑特殊工种)最新版教材汇编出起重信号司索工(建筑特殊工种)仿…

5、Docker安装mysql主从复制与redis集群

安装mysql主从复制 主从搭建步骤 1.1 新建主服务器容器实例3307 docker run -p 3307:3306 --name mysql-master #3307映射到3306&#xff0c;容器名为mysql-master -v /app/mysql/mydata/mysql-master/log:/var/log/mysql #容器数据卷 -v /app/mysql/mydata/mysql-master/dat…