当前位置: 首页 > 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接…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...