数据结构6.4——归并排序
基本思想:
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为,称为二路归并。
核心思想:
将两个已经排好序的数组,合成一个排好序的数组
如果:一个数组只有一个元素,那么这个数组一定是有序的
问题:
- 我们该如何把一个乱序的数组,分为全是只有一个元素的数组?(答案:递归)
- 我们又该如何把多个只有一个元素的数组合并成一个有序的数组?
代码演示:
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc::fail");return;}_MergeSort(a, 0, n - 1, tmp);
}void _MergeSort(int* a, int begin, int end, int* tmp)
{if(begin>=end)//当只有一个元素排序时候就停止了,毕竟数组只有一个元素就相当于排好序了return;int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);//递归的目的是把数组打散_MergeSort(a, mid+1, end, tmp);int begin1 = begin, end1 = mid;//将两个排好序的数组,变成一个排序序的数组int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2];}}while (begin1 <= end1)//当其中的一个数组走完,但另一个数组没走完,就把剩下的数组的数据插入就行{tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin - 1));
}
归并排序的特性总结:
- 归并的缺点在于需要O(N)的空间复杂度,归并排序的思想更多的是解决再磁盘中的外排序问题
- 时间复杂度:O(NlogN)
- 空间复杂度:O(N)
- 稳定性:稳定
相关文章:

数据结构6.4——归并排序
基本思想: 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个…...
【html 常用MIME类型列表】
本表仅列出了常用的MIME类型,完整列表参考文档。 浏览器通常使用 MIME 类型(而不是文件扩展名)来确定如何处理 URL,因此 Web 服务器在响应头中添加正确的 MIME 类型非常重要。 如果配置不正确,浏览器可能会曲解文件内容…...

Linux之vim编辑器
vi编辑器是所有Unix及linux系统下标准的编辑器,类似于Windows系统下的记事本。很多软件默认使用vi作为他们编辑的接口。vim是进阶版的vi,vim可以视为一种程序编辑器。 前言: 1.文件准备 复制 /etc/passwd文件到自己的目录下(不…...

【工具介绍】可以批量查看LableMe标注的图像文件信息~
在图像处理和计算机视觉领域,LabelMe是一个广泛使用的图像标注工具,它帮助我们对图像中的物体进行精确的标注。但是,当标注完成后,我们常常需要一个工具来批量查看这些标注信息。 今天,我要介绍的这款exe程序…...
2024年山西省第十八届职业院校技能大赛 (高职组)“信息安全管理与评估”赛项规程
2024年山西省第十八届职业院校技能大赛 (高职组)“信息安全管理与评估”赛项规程 一、赛项名称 赛项名称:信息安全管理与评估 英文名称:Information Security Management and Evaluation 赛项组别:高职教师组 赛项归属…...

STM32完全学习——STemWin的移植小插曲
一、移植编译的一些问题 新版的STemWin的库没有区别编译器,只有一些这样的文件,默认你将这些文件导入到KEIL中,然后编译就会有下面的错误。 ..\MEWIN\STemWin\Lib\STemWin_CM4_wc16.a(1): error: A1167E: Invalid line start ..\MEWIN\STe…...

Java——IO流(下)
一 (字符流扩展) 1 字符输出流 (更方便的输出字符——>取代了缓冲字符输出流——>因为他自己的节点流) (PrintWriter——>节点流——>具有自动行刷新缓冲字符输出流——>可以按行写出字符串,并且可通过println();方法实现自动换行) 在Java的IO流中…...
avue-crud 同时使用 column 与 group 的问题
场景一:在使用option 中的column 和 group 进行表单数据新增操作时,进行里面的控件操作时,点击后卡死问题,文本没问题 其它比如下拉,单选框操作,当删除 column 中的字段后, group 中的可以操作 …...
深入解析 Pytest 中的 conftest.py:测试配置与复用的利器
在 Pytest 测试框架中,conftest.py 是一个特殊的文件,用于定义测试会话的共享配置和通用功能。它是 Pytest 的核心功能之一,可以用于以下目的: 【主要功能】 1、定义共享的 Fixture (1)conftest.py 文件可…...

JAVA |日常开发中Websocket详解
JAVA |日常开发中Websocket详解 前言一、Websocket 概述1.1 定义1.2 优势 二、Websocket 协议基础2.1 握手过程2.2 消息格式2.3 数据传输方式 三、Java 中使用 Websocket3.1 Java WebSocket API(JSR - 356)3.2 第三方库(如 Tyrus&…...

Typora教程
目录 一、下载安装 二、激活 1.激活 2.解决激活提示窗口 一、下载安装 去官网下载Typora安装,我的是1.9.5版本 二、激活 1.激活 根据路径找到Typora/resources/page-dist/static/js 使用记事本打开LicenseIndex文件,如下图: 按住快捷…...

泛微E9常见API保姆级详解!!!!
前言 在泛微前端开发过程中,虽然大部分是对流程以及流程逻辑的调整,但是还是会有一些小的个性化需求是需要借助JS来实现的。 比如:对同一组数据,前后变化不一样时,需要对这组变化后的数据进行标红处理;对提…...
UniApp配置使用原子化tailwindcss
参考视频 创建项目 新建项目选择uniapp - vue版本这里我选择3 - 点击创建即可 创建完成后,如果是要编译到小程序的项目则可以先将项目运行到小程序打开了 初始化package.json 执行 npm init -y安装和配置 安装 npm i -D tailwindcss postcss autoprefixer # 安…...

02. Docker:安装和操作
目录 一、Docker的安装方式 1、实验环境准备 1.1 关闭防火墙 1.2 可以访问网络 1.3 配置yum源 2、yum安装docker 2.1 安装docker服务 2.2 配置镜像加速 2.3 启动docker服务 3、二进制安装docker 3.1 下载或上传安装包并解压 3.2 配置使用systemctl管理 3.3 配置镜像…...

【MySQL中多表查询和函数】
目录 1.多表查询 1.1 外键 1.2 链接查询 2.MySQL函数 内置函数简介 数值函数 字符串函数 时间日期函数 条件判断操作 开窗函数 1.多表查询 本质:把多个表通过主外键关联关系链接(join)合并成一个大表,在去单表查询操作…...

加速科技精彩亮相ICCAD 2024
12月11日—12日 ,中国集成电路设计业的年度盛会——ICCAD 2024在上海世博馆隆重举行。本次活动以“智慧上海,芯动世界”为主旨,汇聚了众多业界精英,共同探讨集成电路产业的未来。作为半导体测试行业领军企业,加速科技携…...

免费下载 | 2024算网融合技术与产业白皮书
《2024算网融合技术与产业白皮书(2023年)》的核心内容概括如下: 算网融合发展概述: 各国细化算网战略,指引行业应用创新升级。 算网融合市场快速增长,算力互联成为投资新热点。 算网融合产业模式逐渐成型…...

Ubuntu系统下部署大语言模型:Ollama和OpenWebUI实现各大模型的人工智能自由
之前在window下安装过 Ollama和OpenWebUI搭建本地的人工智能web项目(可以看我之前写的文章),无奈电脑硬件配置太低,用qwen32b就很卡,卡出PPT了,于是又找了一台机器安装linux系统,在linux系统下测试一下速度能否可以快一些。 系统硬件介绍 Ubuntu 22.04.4 LTS CPU: i5…...

基于Mybatis,MybatisPlus实现数据库查询分页功能
基于Mybatis,MybatisPlus实现数据库查询分页功能 目录 基于Mybatis,MybatisPlus实现数据库查询分页功能使用Mybatis插件实现分页数据库准备分页插件配置和使用常用数据: 使用MybatisPlus插件实现分页数据库准备分页插件配置和使用自定义分页查…...

【razor】echo搭配relay功能分析
echo 要搭配relay 实现作者说relay在linux上跑,可以模拟丢包、延迟目前没看到如何模拟。relay监听9200,有俩作用 echopeer1 发relay,replay 把peer1的包给peer2 ,实现p2p能力。 接收端:采集后发送发给relay的 接收端的地址就是自己,的地址就是本地的9200,因此是让relay接…...

Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...

7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...

K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...

USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...