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

数据结构6.4——归并排序

基本思想:

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为,称为二路归并。

核心思想:

将两个已经排好序的数组,合成一个排好序的数组

如果:一个数组只有一个元素,那么这个数组一定是有序的

问题:

  1. 我们该如何把一个乱序的数组,分为全是只有一个元素的数组?(答案:递归)
  2. 我们又该如何把多个只有一个元素的数组合并成一个有序的数组?

代码演示:

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));
}

归并排序的特性总结:

  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思想更多的是解决再磁盘中的外排序问题
  2. 时间复杂度:O(NlogN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定

相关文章:

数据结构6.4——归并排序

基本思想&#xff1a; 归并排序是建立在归并操作上的一种有效的排序算法&#xff0c;该算法是采用分治法的一个非常典型的应用。将已有的子序列合并&#xff0c;得到完全有序的序列&#xff1b;即先使每个子序列有序&#xff0c;再使子序列段间有序。若将两个有序表合并成一个…...

【html 常用MIME类型列表】

本表仅列出了常用的MIME类型&#xff0c;完整列表参考文档。 浏览器通常使用 MIME 类型&#xff08;而不是文件扩展名&#xff09;来确定如何处理 URL&#xff0c;因此 Web 服务器在响应头中添加正确的 MIME 类型非常重要。 如果配置不正确&#xff0c;浏览器可能会曲解文件内容…...

Linux之vim编辑器

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

【工具介绍】可以批量查看LableMe标注的图像文件信息~

在图像处理和计算机视觉领域&#xff0c;LabelMe是一个广泛使用的图像标注工具&#xff0c;它帮助我们对图像中的物体进行精确的标注。但是&#xff0c;当标注完成后&#xff0c;我们常常需要一个工具来批量查看这些标注信息。 今天&#xff0c;我要介绍的这款exe程序&#xf…...

2024年山西省第十八届职业院校技能大赛 (高职组)“信息安全管理与评估”赛项规程

2024年山西省第十八届职业院校技能大赛 &#xff08;高职组&#xff09;“信息安全管理与评估”赛项规程 一、赛项名称 赛项名称&#xff1a;信息安全管理与评估 英文名称&#xff1a;Information Security Management and Evaluation 赛项组别&#xff1a;高职教师组 赛项归属…...

STM32完全学习——STemWin的移植小插曲

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

Java——IO流(下)

一 (字符流扩展) 1 字符输出流 (更方便的输出字符——>取代了缓冲字符输出流——>因为他自己的节点流) (PrintWriter——>节点流——>具有自动行刷新缓冲字符输出流——>可以按行写出字符串&#xff0c;并且可通过println();方法实现自动换行) 在Java的IO流中…...

avue-crud 同时使用 column 与 group 的问题

场景一&#xff1a;在使用option 中的column 和 group 进行表单数据新增操作时&#xff0c;进行里面的控件操作时&#xff0c;点击后卡死问题&#xff0c;文本没问题 其它比如下拉&#xff0c;单选框操作&#xff0c;当删除 column 中的字段后&#xff0c; group 中的可以操作 …...

深入解析 Pytest 中的 conftest.py:测试配置与复用的利器

在 Pytest 测试框架中&#xff0c;conftest.py 是一个特殊的文件&#xff0c;用于定义测试会话的共享配置和通用功能。它是 Pytest 的核心功能之一&#xff0c;可以用于以下目的&#xff1a; 【主要功能】 1、定义共享的 Fixture &#xff08;1&#xff09;conftest.py 文件可…...

JAVA |日常开发中Websocket详解

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

Typora教程

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

泛微E9常见API保姆级详解!!!!

前言 在泛微前端开发过程中&#xff0c;虽然大部分是对流程以及流程逻辑的调整&#xff0c;但是还是会有一些小的个性化需求是需要借助JS来实现的。 比如&#xff1a;对同一组数据&#xff0c;前后变化不一样时&#xff0c;需要对这组变化后的数据进行标红处理&#xff1b;对提…...

UniApp配置使用原子化tailwindcss

参考视频 创建项目 新建项目选择uniapp - vue版本这里我选择3 - 点击创建即可 创建完成后&#xff0c;如果是要编译到小程序的项目则可以先将项目运行到小程序打开了 初始化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.多表查询 本质&#xff1a;把多个表通过主外键关联关系链接&#xff08;join&#xff09;合并成一个大表&#xff0c;在去单表查询操作…...

加速科技精彩亮相ICCAD 2024

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

免费下载 | 2024算网融合技术与产业白皮书

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

Ubuntu系统下部署大语言模型:Ollama和OpenWebUI实现各大模型的人工智能自由

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

基于Mybatis,MybatisPlus实现数据库查询分页功能

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

【razor】echo搭配relay功能分析

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

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...