【数据结构】归并排序

👦个人主页:Weraphael
✍🏻作者简介:目前正在学习c++和算法
✈️专栏:数据结构
🐋 希望大家多多支持,咱一起进步!😁
如果文章有啥瑕疵
希望大佬指点一二
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注😍
目录
- 一、基本思想(递归)
- 二、归并的方式(双指针算法)
- 三、递归代码实现
- 四、非递归版归并排序
- 4.1 思路
- 4. 2 代码实现
一、基本思想(递归)

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。有点类似于二叉树的后序遍历。
归并排序前提是两个序列必须是有序,然后再从两个序列中选数到一个临时数组中。
以下是归并排序的核心步骤:
- 确定分界点。目的是为了分为两个序列。
mid = (left + right) >> 1 - 递归处理分界点的左右两部分的区间。
[left, mid] [mid + 1, right] - 【✨重点✨】归并。如上图所示,当递归至区间只有一个数后,开始将两个有序序列合并成一个有序序列
二、归并的方式(双指针算法)

- 使用两个指针
i和j, 分别指向分界点两端的数组头。 - 创建一个临时数组
tmp来暂存排完有序的数组,用k来遍历tmp。 - 比较
a[i]和a[j]直到其中一个序列中的元素全部遍历完。这就分为两种情况:若a[i]<=a[j],则tmp[k++] = a[i++](将小的元素放入tmp中);同理,若a[i] > a[j],则tmp[k++] = a[j++] - 可能会存在特殊情况:左、右两个区间可能会有多余元素没有比较完,则将多余元素原封不动放入数组
tmp - 最后再将
tmp数组中的元素复制回原数组a[]
三、递归代码实现
void RMergeSort(int a[], int l, int r, int* tmp)
{// 当区间只有一个数或者没有数,没必要排序了if (l >= r) return;// 1. 确定分界点下标int mid = (l + r) >> 1;// 2. 递归处理分界点左右两端区间RMergeSort(a, l, mid, tmp);RMergeSort(a, mid + 1, r, tmp);// 当递归结束来到此处,说明分界点左右两边已经是有序的了// 3. 归并int i = l, j = mid + 1;int k = 0;while (i <= mid && j <= r){if (a[i] <= a[j])tmp[k++] = a[i++];elsetmp[k++] = a[j++];}// 可能存在某个区间没有遍历完while (i <= mid)tmp[k++] = a[i++];while (j <= r)tmp[k++] = a[j++];// 将已排好序tmp还给原数组afor (int i = l, k = 0; i <= r; i++, k++)a[i] = tmp[k];
}// 归并排序(递归)
void MergeSort(int a[], int n)
{int* tmp = new int[n];// 如果在此函数递归,每次都要new大小为n的对象,消耗太大RMergeSort(a, 0, n - 1, tmp);delete[] tmp;
}
四、非递归版归并排序
4.1 思路
归并排序的非递归实现通常使用迭代和循环来模拟递归过程。下面是归并排序非递归实现的基本思路:
-
分组: 首先,将原始数组视为若干个长度为1的有序子数组(因为长度为1的数组是有序的)。
-
两两合并: 然后进行迭代,将相邻的两个有序子数组进行合并,并按照合并后的顺序形成新的有序子数组。这一步可以通过循环实现。
-
增加子数组长度: 接着,将子数组长度翻倍,重复上述合并操作,直到整个数组成为一个有序的数组。

值得注意的是,归并排序的非递归实现需要考虑如何处理边界情况、子数组长度变化等细节,但整体思路和递归实现是类似的。
4. 2 代码实现
void mergeSort(int a[], int l, int r, int n)
{// 辅助数组int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;while (gap < n){for (int i = 0; i <= r; i = i + 2 * gap){int begin1 = i, end1 = i + gap - 1, mid = i + gap - 1;int begin2 = mid + 1, end2 = i + 2 * gap - 1;int j = i;if (begin2 > r) break;if (end2 > r) end2 = r;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++];}for (int j = i; j <= end2; j++){a[j] = tmp[j];}}gap = 2 * gap;}
}
相关文章:
【数据结构】归并排序
👦个人主页:Weraphael ✍🏻作者简介:目前正在学习c和算法 ✈️专栏:数据结构 🐋 希望大家多多支持,咱一起进步!😁 如果文章有啥瑕疵 希望大佬指点一二 如果文章对你…...
数字引领,智慧赋能|袋鼠云与易知微共同亮相2023智慧港口大会
2023年10月19日,由中国港口协会、中国交通通信信息中心、天津港(集团)有限公司主办,中国港口协会智慧港口专业委员会、《港口科技》杂志社等单位承办的以“数字引领 智慧赋能”为主题的“2023智慧港口大会”在天津顺利召开。 袋鼠…...
星火模型(Spark)的langchain 实现
星火模型的langchain实现 测试已通过,希望有所帮助。 使用前请先安装环境: pip install githttps://github.com/shell-nlp/spark-ai-python.git注意: 一定要使用上面方式安装spark库,因对官方的库做了改动。官方的库已经长时间不…...
python运算符重载之构造函数和迭代器
1 python运算符重载之构造函数和迭代器 python运算符重载是在类方法中拦截内置操作-当类的实例使用内置操作时,pytho自动调用对应方法,并且返回操作结果。 NO#描述1拦截运算运算符重载拦截内置操作,比如打印、函数调用、点号运算、表达式运…...
【数据处理】Python:实现求条件分布函数 | 求平均值方差和协方差 | 求函数函数期望值的函数 | 概率论
猛戳订阅! 👉 《一起玩蛇》🐍 💭 写在前面:本章我们将通过 Python 手动实现条件分布函数的计算,实现求平均值,方差和协方差函数,实现求函数期望值的函数。部署的测试代码放到文后了,运行所需环境 python version >= 3.6,numpy >= 1.15,nltk >= 3.4,tqd…...
new/delete 和malloc/free的区别
C中: 创建单个数据空间: char *ch new char; delete ch; ch NULL; 创建多个数据空间: char *ch new char[4]; delete [] ch; ch NULL; C语言中: 创建单个数据空间: char *ch malloc(sizeof(char)); fre…...
Linux程序设计(上)
系列文章目录 文章目录 系列文章目录前言一、unix, linux, GNU, POSIXLinux程序 二、shellshell语法1.变量2.语句 函数命令命令的执行dialog工具-- 三、文件操作1. Linux 文件结构2. 系统调用和设备驱动程序3. 库函数4. 底层文件访问5. 标准I/O库6.格式化输入输出7. 文件和目录…...
mysql面试题——存储引擎相关
一:MySQL 支持哪些存储引擎? MySQL支持多种存储引擎,比如InnoDB,MyISAM, MySQL大于等于5.5之后,默认存储引擎是InnoDB 二:InnoDB 和 MyISAM 有什么区别? InnoDB支持事务,MyISAM不支持InnoD…...
趣学python编程 (四、数据结构和算法介绍)
数据结构和算法在编程中非常重要。数据结构是组织和存储数据的方式,而算法是解决问题的方法和步骤。你要挑战的蓝桥杯,实际也是在设计算法解决问题。其实各种编程语言都只是工具,而程序的核心数据结构算法。犹如练武,数据结构和算…...
使用Pandas进行时间重采样,充分挖掘数据价值
大家好,时间序列数据蕴含着很大价值,通过重采样技术可以提升原始数据的表现形式。本文将介绍数据重采样方法和工具,提升数据可视化技巧。 在进行时间数据可视化时,数据重采样是至关重要且非常有用的,它支持控制数据的…...
Django(九、choices参数的使用、多对多表的三种创建方式、Ajax技术)
文章目录 一、choices参数choices参数的用法choices 参数用法总结 二、MVC与MTV模式1.MVC2.MTV 三、多对多的三种创建方式1.全自动创建2.纯手动创建半自动创建 四、Django与Ajax1.什么是Ajax常见的场景Ajax案例 一、choices参数 在没有用到choices参数之前,我们在D…...
德语B级SampleAcademy
德语B级 一, 反身代词(1)A 主语和宾语一致(2)D 双宾语,主语与直接宾语不一致(3), 补充单词(4)真反身代词(5)假反身代词(6)真假反身代词(7)相互反身(8)非反身#反身#相互反身 二,Nomen…...
vue3自定义hooks
获取dom的id属性 index.ts import { onMounted } from "vue" type option {el: string }export default function(option:option):Promise<{name: string}> {return new Promise((resolve)>{onMounted(()>{const dom:HTMLElement document.querySele…...
Consistency Models 阅读笔记
简介 Diffusion models需要多步迭代采样才能生成一张图片,这导致生成速度很慢。一致性模型(Consistency models)的提出是为了加速生成过程。 Consistency models可以直接一步采样就生成图片,但是也允许进行多步采样来提高生成的质…...
杭电oj 2034 人见人爱A-B C语言
此处的c和a指向同一块内存空间,改变c就是改变a,反之亦然,此处是为了方便看这么写的,如果不想c和a指向同一空间请分别开辟空间(即不如此写camalloc) #include<stdio.h> #include<stdlib.h>int …...
springboot(ssm大学生成绩管理系统 成绩管理平台Java(codeLW)
springboot(ssm大学生成绩管理系统 成绩管理平台Java(code&LW) 开发语言:Java 框架:ssm/springboot vue JDK版本:JDK1.8(或11) 服务器:tomcat 数据库:mysql 5.7(或8.0&…...
SOME/IP 协议介绍(五)指南
指南(信息性) 选择传输协议 SOME/IP直接支持互联网上使用最广泛的两种传输协议:用户数据报协议(UDP)和传输控制协议(TCP)。UDP是一种非常简洁的传输协议,仅支持最重要的功能&#…...
Python调用企微机器人: 发送常用格式汇总
企微接口文档 发送应用消息 - 接口文档 - 企业微信开发者中心 发送格式 应用支持推送文本、图片、视频、文件、图文等类型。 ~~~以下列举常用格式 示例~~~ 1.发送文本 代码如下: def sendtxt_robotmsg(self):# 正式keywx_key "xx"wx_webhookurl htt…...
论文阅读——DiffusionDet
在目标检测上使用扩散模型 前向过程:真实框-->随机框 后向过程:随机框-->真实框 前向过程: 一般一张图片真实框的数目不同,填补到同一的N个框,填补方法可以是重复真实框,填补和图片大小一样的框&a…...
elmenetui表格二次封装包含查询框和分页
<!--dataList: 表格数据columnList: 表头字段 宽度minWidth使用slotName字段: 需要对列数据进行处理,不写prop字段,使用slotName字段btnText<String>: 按钮字段btnIcon<String>: 按钮的iconbtnEvent: 按钮事件btnType: 按钮类型getHeigh…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
Linux 下 DMA 内存映射浅析
序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存,但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程,可以参考这篇文章,我觉得写的非常…...
前端高频面试题2:浏览器/计算机网络
本专栏相关链接 前端高频面试题1:HTML/CSS 前端高频面试题2:浏览器/计算机网络 前端高频面试题3:JavaScript 1.什么是强缓存、协商缓存? 强缓存: 当浏览器请求资源时,首先检查本地缓存是否命中。如果命…...
