当前位置: 首页 > 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%; }...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

Monorepo架构: Nx Cloud 扩展能力与缓存加速

借助 Nx Cloud 实现项目协同与加速构建 1 &#xff09; 缓存工作原理分析 在了解了本地缓存和远程缓存之后&#xff0c;我们来探究缓存是如何工作的。以计算文件的哈希串为例&#xff0c;若后续运行任务时文件哈希串未变&#xff0c;系统会直接使用对应的输出和制品文件。 2 …...

嵌入式面试常问问题

以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...

Android Framework预装traceroute执行文件到system/bin下

文章目录 Android SDK中寻找traceroute代码内置traceroute到SDK中traceroute参数说明-I 参数&#xff08;使用 ICMP Echo 请求&#xff09;-T 参数&#xff08;使用 TCP SYN 包&#xff09; 相关文章 Android SDK中寻找traceroute代码 设备使用的是Android 11&#xff0c;在/s…...

[10-1]I2C通信协议 江协科技学习笔记(17个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17...

结合PDE反应扩散方程与物理信息神经网络(PINN)进行稀疏数据预测的技术方案

以下是一个结合PDE反应扩散方程与物理信息神经网络(PINN)进行稀疏数据预测的技术方案,包含完整数学推导、PyTorch/TensorFlow双框架实现代码及对比实验分析。 基于PINN的反应扩散方程稀疏数据预测与大规模数据泛化能力研究 1. 问题定义与数学模型 1.1 反应扩散方程 考虑标…...