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

数据结构之归并排序算法【图文详解】

P. S.:以下代码均在VS2019环境下测试,不代表所有编译器均可通过。
P. S.:测试代码均未展示头文件stdio.h的声明,使用时请自行添加。

  

在这里插入图片描述

                                           博主主页:LiUEEEEE
                                              C语言专栏
                                            数据结构专栏
                                         力扣牛客经典题目专栏

目录

  • 1、归并排序的基本思想
  • 2、归并排序的实现
    • 2.1. 归并排序的递归实现
    • 2.2. 归并排序的非递归实现
  • 3、归并排序非递归方法实现的常见问题
  • 4、结语

1、归并排序的基本思想


  归并排序的基本思想:
  • 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:
    在这里插入图片描述



2、归并排序的实现


  归并排序的实现拥有两种方法:
  • 递归实现
  • 非递归实现

  但归根到底其主要思想不会发生变化,以下是归并排序的动态展示图:
在这里插入图片描述

2.1. 归并排序的递归实现


  如上文所展示的效果图可知:
  • 对于归并排序,需使用二叉树中后序的思想,将所给目标数组全部类二分,而后进行递归,当所递归数组个数为1时开始归并。
  • 将归并后的子数组复制到原数组中对应位置,并开启新一轮的归并,这就需要我们动态开辟一个第三方数组tmp来进行辅助。

  
  • 归并排序的递归实现代码如下所示:
void MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end)return;int mid = (begin + end) / 2;MergeSort(a, tmp, begin, mid);MergeSort(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));
}

2.2. 归并排序的非递归实现


  其思想与递归并无差别,区别在于操作方式:
  • 在递归实现中,我们使用类二分的方法将原目标数组分为2份依次进行二分的归并递归,而在非递归中,我们不再使用类二分的方法,而是直接在原数组上进行操作。
  • 在逻辑上认为原数组已经进行处于递归的过程,即:令gap = 1
  • 第一次对每一个元素进行归并,归并完成后,令 gap *= 2。
  • 第二次对每两个元素进行归并,归并完成后,令 gap *= 2。
  • 第n 次对每2^(n-1)个元素进行归并,归并完成后,令 gap *= 2。
  • 直到gap大于元素原本数组个数时,结束。
    在这里插入图片描述
  • 归并排序的非递归实现代码如下:
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("MergeSortNonR: malloc fail");return;}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 + 2 * gap - 1;if (begin2 >= n)对程序代码的优化,防止越界break;if (end2 >= n)对程序代码的优化,防止越界end2 = n - 1;int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2])tmp[j++] = a[begin1++];elsetmp[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));}printf("\n");gap *= 2;}free(tmp);tmp = NULL;
}




3、归并排序非递归方法实现的常见问题


  在使用非递归方法实现归并排序时,我们通常无法精确掌握其归并数组的左右区间,例如下图:

在这里插入图片描述
  图中所展示的示例数组拥有十九个元素,但在归并过程中会发生越界行为,出现bug。

  但通过途中所展示我们不难发现,出现越界的数组一般为右子数组,当右子树组的右下标出现越界时,我们可直接对其右下标进行修正即可,当右子树组的左下标越界时,就说明左子数组已经归并完成,我们可直接跳出循环进行下一次归并,直到整个数组归并完成即可。




4、结语


在这里插入图片描述

  十分感谢您观看我的原创文章。
  本文主要用于个人学习和知识分享,学习路漫漫,如有错误,感谢指正。
  如需引用,注明地址。

相关文章:

数据结构之归并排序算法【图文详解】

P. S.&#xff1a;以下代码均在VS2019环境下测试&#xff0c;不代表所有编译器均可通过。 P. S.&#xff1a;测试代码均未展示头文件stdio.h的声明&#xff0c;使用时请自行添加。 博主主页&#xff1a;LiUEEEEE                        …...

设计模式基础

什么是设计模式 设计模式是一种在软件设计过程中反复出现的问题和相应解决方案的描述。它是一种被广泛接受的经验总结&#xff0c;可以帮助开发人员解决常见的设计问题并提高代码的重用性、可维护性和可扩展性。 设计模式可以分为三类&#xff1a; 创建型模式&#xff08;Crea…...

Glide支持通过url加载本地图标

序言 glide可以在load的时候传入一个资源id来加载本地图标&#xff0c;但是在开发过程中。还得区分数据类型来分别处理。这样的使用成本比较大。希望通过自定义ModelLoader实现通过自定义的url来加载Drawab。降低使用成本 实现 一共四个类 类名作用GlideIcon通过自定义url的…...

网络安全形势与WAF技术分享

我一个朋友的网站&#xff0c;5月份时候被攻击了&#xff0c;然后他找我帮忙看看&#xff0c;我看他的网站、网上查资料&#xff0c;不看不知道&#xff0c;一看吓一跳&#xff0c;最近几年这网络安全形势真是不容乐观&#xff0c;在网上查了一下资料&#xff0c;1、中国信息通…...

【实战JVM】-实战篇-06-GC调优

文章目录 1 GC调优概述1.1 调优指标1.1.1 吞吐量1.1.2 延迟1.1.3 内存使用量 2 GC调优方法2.1 发现问题2.1.1 jstat工具2.1.2 visualvm插件2.1.3 PrometheusGrafana2.1.4 GC Viewer2.1.5 GCeasy 2.2 常见GC模式2.2.1 正常情况2.2.2 缓存对象过多2.2.3 内存泄漏2.2.4 持续FullGC…...

深入解析智慧互联网医院系统源码:医院小程序开发的架构到实现

本篇文章&#xff0c;小编将深入解析智慧互联网医院系统的源码&#xff0c;重点探讨医院小程序开发的架构和实现&#xff0c;旨在为相关开发人员提供指导和参考。 一、架构设计 智慧互联网医院系统的架构设计是整个开发过程的核心&#xff0c;直接影响到系统的性能、扩展性和维…...

获取 Bean 对象更加简单的方式

获取 bean 对象也叫做对象装配&#xff0c;是把对象取出来放到某个类中&#xff0c;有时候也叫对象注⼊。 对象装配&#xff08;对象注⼊&#xff09;即DI 实现依赖注入的方式有 3 种&#xff1a; 1. 属性注⼊ 2. 构造⽅法注⼊ 3. Setter 注⼊ 属性注入 属性注⼊是使⽤ Auto…...

ChatGPT基本原理

技术背景与基础&#xff1a; 深度学习&#xff1a;ChatGPT建立在深度学习技术之上&#xff0c;通过复杂的神经网络结构模拟人类的语言处理过程。深度学习使得ChatGPT能够处理海量的文本数据&#xff0c;并从中提取出复杂的语言模式和规律。GPT架构&#xff1a;ChatGPT基于GPT&a…...

几种更新 npm 项目依赖的实用方法

几种更新 npm 项目依赖的实用方法 引言1. 使用 npm update 命令2. 使用 npm-check-updates 工具3. 使用 npm outdated 命令4. 直接手动更新 package.json 文件5. 直接安装最新版本6. 使用自动化工具结语 引言 在软件开发的过程中&#xff0c;我们知道依赖管理是其中一个至关重…...

Python爬虫之简单学习BeautifulSoup库,学习获取的对象常用方法,实战豆瓣Top250

BeautifulSoup是一个非常流行的Python库&#xff0c;广泛应用于网络爬虫开发中&#xff0c;用于解析HTML和XML文档&#xff0c;以便于从中提取所需数据。它是进行网页内容抓取和数据挖掘的强大工具。 功能特性 易于使用: 提供简洁的API&#xff0c;使得即使是对网页结构不熟悉…...

SAP-BASIS15-查看系统状态

...

前端怎么debugger排查线上问题

前端怎么debugger排查线上问题 1.问题背景2.问题详细说明3.处理方案a.开发环境怎么找&#xff0c;步骤一样的&#xff1a;b.生产环境怎么找&#xff0c;步骤一样的&#xff1a;还有一种情况就是你的子盒子是使用csshover父盒子出来的&#xff0c; 4.demo地址&#xff1a; 1.问题…...

LabVIEW源程序安全性保护综合方案

LabVIEW源程序安全性保护综合方案 一、硬件加密保护方案 选择和安装硬件设备 选择加密狗和TPM设备&#xff1a;选择Sentinel HASP加密狗和支持TPM&#xff08;可信平台模块&#xff09;的计算机主板。 安装驱动和开发工具&#xff1a;安装Sentinel HASP加密狗的驱动程序和开发…...

JS包装类:循环中为什么建议用变量存储str.length进行循环判断?

前言 在Javascript通常我们在遍历一个字符串的时候通常使用的方式是 var str "abcdefg"; for(let i0;i<str.length;i){}但在最近的学习中&#xff0c;有人建议我最好应该是下面这样执行。 var str "abcdefg"; for(let i0,len str.length;i<len;i)…...

Android Audio实战——音量默认值修改(一)

在前面的文章《音频配置加载》中我们知道了,Audio 的一些配置信息是由硬件驱动保存到 audio_policy_configuration.xml 文件中,音量的一些默认值也会如此。但是在一些车载设备开发中,需要适配不同车型的需求,一套代码通常要适配多个车型,这就需要在 FW 层进行一些默认值的…...

解决uni-app progress控件不显示问题

官方代码&#xff1a; <view class"progress-box"><progress :percent"80" show-info activeColor"red" stroke-width"10" /> </view> 进度条并不在页面中显示&#xff0c;那么我们需要给进度条加上宽高style"…...

使用C++版本的opencv dnn 部署onnx模型

使用OpenCV的DNN模块在C中部署ONNX模型涉及几个步骤&#xff0c;包括加载模型、预处理输入数据、进行推理以及处理输出。 构建了yolo类&#xff0c;方便调用 yolo.h 文件 #ifndef YOLO_H #define YOLO_H #include <fstream> #include <sstream> #include <io…...

python中实现队列功能

【小白从小学Python、C、Java】 【考研初试复试毕业设计】 【Python基础AI数据分析】 python中实现队列功能 选择题 以下代码最后一次输出的结果是&#xff1f; from collections import deque queue deque() queue.append(1) queue.append(2) queue.append(3) print(【显示】…...

自然资源-关于城镇开发边界局部优化的政策思路梳理

自然资源-关于城镇开发边界局部优化的政策思路梳理 国土空间规划的核心之一是要统筹划定“三区三线”&#xff0c;三条控制线中的城镇开发边界的划定与优化工作&#xff0c;一直是国土空间规划改革的重要组成部分&#xff0c;其有助于遏制城市盲目扩张&#xff0c;强化底线约束…...

ElementUI的Table组件在无数据情况下让“暂无数据”文本居中显示

::v-deep .el-table__empty-block {width: 100%;min-width: 100%;max-width: 100%; }...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...