数据结构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接…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...

tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...