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

【排序算法】归并排序

目录

一.基本思想

二.递归版本

三.非递归版本

四.特性总结

1.时间复杂度:O(N*logN)

2.空间复杂度:O(N)

3.稳定性:稳定


一.基本思想

归并排序是采用分治法的一个非常典型的应用。它将已经有序的序列合并为完全有序的序列,即先使得每一个子序列有序,再让子序列之间有序。归并排序建立在归并操作上,以下动图能很好的演示归并排序中归并的过程:

但上图只展示了归并排序中归并的过程,没有对拆分过程的展示,接下来我将具体介绍归并排序的核心步骤。

已知对于两个已经有序的序列而言,使用p1和p2来比较,p1和p2中较小的一个一定就是当前最小的,放入临时数组tmp中,随后指向的p向后移动,再次进行比较,如此就能将两个有序的序列合并为一个有序序列,这就做到了排序。

然而,如何得到两个已经有序的序列呢?这是类似问题,与排序整个序列的主问题是类似的,很明显,已经可以猜到要使用递归来实现了,那么只需要将两个无序序列进行再次拆分,直到序列中仅剩一个数据,那么此时就可以看作是有序的了,这就是拆分过程。 

拆分结束后,就进行归并,每两个已有序的序列合并到一起,再和其他已合并的序列进行合并,最终合并为一个序列,这就是排序后得到的最终结果,下图展示了整个过程:

 具体应该如何拆分?拆分也是有讲究的,不注意会产生问题。一般都会想到取中分割,取序列左端为begin,右端为end,mid自然等于(begin+end)/2,那么就可以围绕mid拆分为左右两个序列,其中mid应该包含在左端,否则会造成死循环,也就是应该分为[begin,mid]和[mid+1,end],证明如下:

二.递归版本

//归并排序-主体
void _Merge(int* a, int* tmp, int begin, int end)
{//结束条件if (begin >= end)return;//拆分int mid = (begin + end) / 2;_Merge(a, tmp, begin, mid);_Merge(a, tmp, mid + 1, end);//归并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, (end - begin + 1) * sizeof(int));
}//归并排序
void Merge(int* a, int n)
{//创建临时数组int* tmp = (int*)malloc(sizeof(int) * n);_Merge(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}

三.非递归版本

对于非递归版本,就不用考虑拆分的过程了,直接将一个数组看作单个有序的状态开始归并。使用gap来模拟归并的过程,如下所示:

根据上述过程可以得到以下代码,但这样的写法却存在一些问题 ,不妨打印出来看看

//归并排序-主体-(非递归)
void Merge_NonR(int* a, int n)
{//创建临时数组int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//gap控制每组归并的数据个数int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;printf("[%d %d],[%d,%d]", begin1, end1, begin2, end2);int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;printf("\n");}
}

 

可以很明显的看到,在只有10个数据的时候(有效下标为0到9),发生了数组越界的问题 ,那么这就还需要在程序中加入对应的解决方法,从上图可以发现,只要是begin2(上图的10和12)出现了越界(大于等于n)那么后一个序列就是非法的,也就不用归并了,此时可以直接跳出循环直接到下一个gap,那么到最后一轮,end2是越界的(如上图15)此时8到9是有序的,只需要调整end2为9(即n-1)即可。完整实现的代码如下:

//归并排序-主体-(非递归)
void Merge_NonR(int* a, int n)
{//创建临时数组int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//gap控制每组归并的数据个数int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;if (begin2 >= n)break;if (end2 >= n)end2 = n - 1;printf("[%d %d],[%d,%d]", begin1, end1, begin2, end2);int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;printf("\n");}
}

四.特性总结

1.时间复杂度:O(N*logN)

依据二分往下递归,类似于二叉树,总共有LogN层,每层总的归并合计起来可以看作O(N),因此总的时间复杂度可以看作是:O(N*logN)

2.空间复杂度:O(N)

由于开辟了一个大小为N的额外数组,因此归并排序的空间复杂度为O(N)

3.稳定性:稳定

相关文章:

【排序算法】归并排序

目录 一.基本思想 二.递归版本 三.非递归版本 四.特性总结 1.时间复杂度&#xff1a;O(N*logN) 2.空间复杂度&#xff1a;O(N) 3.稳定性&#xff1a;稳定 一.基本思想 归并排序是采用分治法的一个非常典型的应用。它将已经有序的序列合并为完全有序的序列&#xff0c;即…...

游戏AI的创造思路-技术基础-决策树(2)

上一篇写了决策树的基础概念和一些简单例子&#xff0c;本篇将着重在实际案例上进行说明 目录 8. 决策树应用的实际例子 8.1. 方法和过程 8.1.1. 定义行为 8.1.2. 确定属性 8.1.3. 构建决策树 8.1.4. 实施行为 8.1.5. 实时更新 8.2. Python代码 8. 决策树应用的实际例子…...

vue缓存页面,当tab切换时保留原有的查询条件

需求&#xff1a; 切换tab时&#xff0c;查询条件不变 路由页面&#xff1a; 单个页面上加这句话&#xff1a;...

PythonConda系列(亲测有效):【解决方案】Collecting package metadata (current_repodata.json): failed

【解决方案】Collecting package metadata (current_repodata.json&#xff09;: failed 问题描述解决方案小结参考文献 问题描述 在cmd下运行&#xff1a;conda install pylint -y&#xff0c;报错如下&#xff1a; C:\Users\apr> conda install --name apr pylint -y Co…...

web前端开发——标签一(注释、标题、段落、换行、格式、图片)

今天我来针对web前端开发讲解标签一 目录 html标签_标题&段落&换行 注释标签&#xff1a;Ctrl/ 标题标签&#xff1a; h1-h6 段落标签&#xff1a; 换行标签: 格式标签 图片标签_src属性 html标签_标题&段落&换行 注释标签&#xff1a;Ctrl/ Ctrl/ &…...

Django 常见的操作符

在filter() 方法&#xff0c;exclude() 方法中使用大于&#xff0c;小于&#xff0c;模糊匹配等操作符。 常见的操作符如下&#xff1a; 操作符含义示例等于Book.objects.filter(price10)! 或 __ne不等于用于查找字段不等于特定值的记录。但更常用exclude()方法。__gt大于用于…...

AJAX是什么?原生语法格式?jQuery提供分装好的AJAX有什么区别?

ajax 的全称 Asynchronous JavaScript and XML (异步 JavaScript 和 XML)。 AJAX是一种创建交互式网页应用的网页开发技术。其中最核心的依赖是浏览器提供的 XMLHttpRequest 对象&#xff0c;是这个对象使得浏览器可以发出 HTTP 请求与接收 HTTP 响应。实现了在页 面不刷新的…...

docker基础知识以及windows上的docker desktop 安装

记录以供备忘 基础概念&#xff1a; 什么是docker 将程序和环境一起打包&#xff0c;以在不同操作系统上运行的工具软件 什么是基础镜像 选一个基础操作系统和语言后&#xff0c;将对应的文件系统、依赖库、配置等打包为一个类似压缩包的文件&#xff0c;就是基础镜像 什么是…...

【深度学习基础】环境搭建 linux系统下安装pytorch

目录 一、anaconda 安装二、创建pytorch1. 创建pytorch环境&#xff1a;2. 激活环境3. 下载安装pytorch包4. 检查是否安装成功 一、anaconda 安装 具体的安装说明可以参考我的另外一篇文章【环境搭建】Linux报错bash: conda: command not found… 二、创建pytorch 1. 创建py…...

【Sql Server】sql server 2019设置远程访问,外网服务器需要设置好安全组入方向规则

大家好&#xff0c;我是全栈小5&#xff0c;欢迎来到《小5讲堂》。 这是《Sql Server》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解。 温馨提示&#xff1a;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 目录 前言1、无法链接…...

idea启动vue项目一直卡死在51%,问题分析及其如何解决

如果你的项目也一直卡在百分之几十&#xff0c;你可以参考下面的方法&#xff0c;试一试能否解决 问题描述&#xff1a; 通过在idea终端中输入命令 npm run serve 启动vue项目&#xff0c;启动进程一直卡在51% 如何解决&#xff1a; 检查 < template > 标签中的html内容…...

基于STM32设计的智能喂养系统(ESP8266+微信小程序)175

基于STM32设计的牛羊喂养系统(微信小程序)(175) 文章目录 一、前言1.1 项目介绍【1】项目功能介绍【2】项目硬件模块组成【3】ESP8266工作模式配置【4】上位机开发【5】项目模块划分1.2 项目功能需求1.3 项目开发背景1.4 开发工具的选择1.5 系统框架图1.6 系统原理图1.7 硬件实…...

第三方支付平台如何完美契合游戏行业?

在数字经济的浪潮中&#xff0c;游戏行业以其独特的魅力和创新能力&#xff0c;成为全球文化和经济交流的重要桥梁。然而&#xff0c;海外游戏商在进军中国市场时&#xff0c;常面临一系列难题。本文将通过一个故事案例&#xff0c;揭示第三方支付平台PASSTO PAY如何帮助海外游…...

计算机网络 5.6网桥与交换机

第六节 网桥与交换机 一、认识网桥 1.功能&#xff1a;连接两个具有相同或相似的网络结构的网络&#xff0c;解决网络之间距离太远问题&#xff0c;提高网络可靠性&#xff0c;还可以起过滤帧的作用而提高网络的性能。 2.适用场合&#xff1a;同构网。 3.特点&#xff1a; …...

CDH实操--集群卸载

作者&#xff1a;耀灵 1、停止正在运行的服务 a、控制台停止集群服务 b、控制台停止Cloudera Management Service c、命令行停止cm服务 systemctl stop cloudera-scm-agent #所有节点执行 systemctl stop cloudera-scm-server #cdh01节点执行2、主线并移除Parcles rm -r…...

5G RedCap调查报告

一、5G RedCap技术背景 5G RedCap(Reduced Capability缩写,轻量化5G),是3GPP标准化组织定义下的5G裁剪版本,是5G面向中高速率连接场景的物联网技术,它的能力介于5G NR(含eMBB和uRLLC)和LPWA(如LTE-M和NR-IoT)之间,如图1所示,是5G-A(5G Advanced)的关键技术之一。…...

模型(卷积、fc、attention)计算量 MAC/FLOPs 的手动统计方法

文章目录 简介背景为什么理解神经网络中的MAC和FLOPs很重要&#xff1f;资源效率内存效率能耗功耗效率 模型优化性能基准研究与发展 FLOPs 和 MACs 定义1. 全连接层 FLOPs 计算步骤 1&#xff1a;识别层参数步骤 2&#xff1a;计算 FLOPs 和 MACs步骤 3&#xff1a;总结结果使用…...

Git 删除包含敏感数据的历史记录及敏感文件

环境 Windows 10 Git 2.41.0 首先备份你需要删除的文件&#xff08;如果还需要的话&#xff09;&#xff0c;因为命令会将本地也删除将项目中修改的内容撤回或直接提交到仓库中&#xff08;有修改内容无法提交&#xff09; 会提示Cannot rewrite branches: You have unstaged …...

vue-tabs标签页引入其他页面

tabs页面 <template> <div class"app-container"> <el-tabs v-model"activeName" type"card" tab-click"handleClick"> <el-tab-pane label"套餐用户列表" name"first"> <user-list r…...

U-net和U²-Net网络详解

目录 U-Net: Convolutional Networks for Biomedical Image Segmentation摘要U-net网络结构pixel-wise loss weight U-Net: Going Deeper with Nested U-Structure for Salient Object Detection摘要网络结构详解整体结构RSU-n结构RSU-4F结构saliency map fusion module -- 显著…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...