【排序算法】——归并排序(递归与非递归)含动图
制作不易,三连支持一下吧!!!
文章目录
- 前言
- 一.归并排序递归方法实现
- 二.归并排序非递归方法实现
前言
这篇博客我们将介绍归并排序的原理和实现过程。
一、归并排序递归方法实现
基本思想:
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
归并排序核心步骤:
1.分解:
将所给序列一分为二,直到区间中只有一个元素时停止。这个过程是递归进行的,通过传递区间参数来控制。
2. 合并:
相邻两个子数组有序之后,就递归合并这两个子数组,将它们合并成一个新的有序子数组。

动图演示如下:

归并时,我们是借助一个临时数组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));
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(n * sizeof(int));_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}
二、归并排序非递归方法实现
同快速排序一样,如果递归深度过深,可能会导致栈溢出,这样的情况下,我们就不能用递归法来实现归并排序。
上篇博客提到:将递归改成非递归的一般方法有两种
一种是直接改循环,如斐波那契数列。
另一种是借助栈或队列,例如快速排序。
这里我们借助栈也无法完成归并排序,因此我们只能选择循环。
代码实现如下:
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc:");return;}int gap = 1;while (gap < n){for (int j = 0; j < n; j +=2*gap){int begin1 = j, end1 = begin1 + gap - 1;int begin2 = end1 + 1, end2 = begin2 + gap - 1;int i = j;if (end1 >= n || begin2 >= n){break;}//处理数组越界的情况if (end2 >= n)end2 = n - 1;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 + j, tmp + j, sizeof(int) * (end2 - j + 1));}gap *= 2;}free(tmp);tmp = NULL;
}
相关文章:
【排序算法】——归并排序(递归与非递归)含动图
制作不易,三连支持一下吧!!! 文章目录 前言一.归并排序递归方法实现二.归并排序非递归方法实现 前言 这篇博客我们将介绍归并排序的原理和实现过程。 一、归并排序递归方法实现 基本思想: 归并排序(MERGE-…...
Mysql自增id、uuid、雪花算法id的比较
MySQL自增id: 优点: 1.简单易用 MySQL自增id 由数据库自动生成。 2.效率高 自增id是按顺序递增的,可以提高插入和查询的效率。 3.索引效率高 自增id可以作为主键或索引列,提高查询效率。 缺点: 1.不适用于分布式系统 在分布式…...
【会议征稿,IEEE出版】第九届信息科学、计算机技术与交通运输国际学术会议(ISCTT 2024,6月28-30)
第九届信息科学、计算机技术与交通运输国际学术会议(ISCTT 2024)将于2024年6月28-30日在中国绵阳举行。 ISCTT 2024将围绕 “信息科学”、"计算机技术”、“交通运输” 等最新研究领域,为来自国内外高等院校、科学研究所、企事业单位的专…...
二十八篇:嵌入式系统实战指南:案例研究与未来挑战
嵌入式系统实战指南:案例研究与未来挑战 1. 引言 1.1 嵌入式系统的重要性及其应用广度 在当今快速发展的技术领域中,嵌入式系统扮演着至关重要的角色。这些系统是专门设计的计算机硬件和软件的组合,旨在执行特定任务,如控制、监…...
探索编程乐趣:绘制螺旋图的奇幻之旅
新书上架~👇全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我👆,收藏下次不迷路┗|`O′|┛ 嗷~~ 目录 一、引言:编程的魔法世界 二、绘制螺旋图的准备工作 三、代码实战:…...
C# 语法糖
语法糖 var关键字(隐式类型变量):自动属性:简化的事件访问器:Lambda表达式和匿名方法:扩展方法:LINQ查询:异步编程(async和await):嵌套匿名类型&a…...
ubuntu 安装VMtool 实现复制粘贴
如果只是安装一个根本没有用,而是两个命令都要安装 sudo apt-get install open-vm-tools sudo apt-get install open-vm-tools-desktop引用博客...
智慧仓储新动力:EasyCVR+AI视频智能监管系统方案助力仓储安全高效管理
一、背景 随着物流行业的快速发展和智能化水平的提升,智慧仓储视频智能监管系统已成为现代仓储管理的重要组成部分。本系统通过综合运用物联网、视频分析、边缘计算等技术手段,实现对仓储环境的全面监控、智能分析和高效管理。 TSINGSEE青犀视频汇聚Ea…...
gcc源码分析(AST抽象语法树)
文章目录 三、AST相关1、AST(抽象语法树)1.1 树结点的声明1.2 树结点的结构1.2.1 tree_node联合体1.2.2 tree_base结构体1.2.3 tree_common结构体1.2.4 常量结构体1.2.5 **标识符节点**2、符号绑定,作用域与block树节点2.1 lang_identifier结构体2.2 c_binding结构体2.3 scop…...
ES基础概念
本文不介绍如何使用ES(使用ES见:) 1.ES生态圈 ES: Logstash:数据处理服务程序,解析转换加工数据; Kibana:数据展示、集群管理,数据可视化、ES管理与监控、报表等…...
断更是我的错
打算在暑假每天两个文章,大概是6月20多号开始吧。...
红队攻防渗透技术实战流程:云安全之云原生安全:云堡垒机
红队云攻防实战 1. 云原生安全-防护设备-云堡垒机1. 云原生安全-防护设备-云堡垒机 堡垒机攻防:(意义) https://mp.weixin.qq.com/s/-WcgyVoTCZuPamVtI5MrJw 堡垒机漏洞:(已知)https://avd.aliyun.com/search?q=%E5%A0%A1%E5%9E%92%E6%9C%BA 云堡垒机:(云攻防) http…...
Down with typename
1. 隐式类型名的详情 C20 之前,typename 在一些其他情况下是不必要的: • 指定继承类的基类型时 • 在构造函数中将初始值传递给基类时 • 在类声明中使用类型成员时 #include <iostream> struct Impl {Impl(){ std::cout << "Impl ctor" &…...
CSS3背景与渐变
背景与渐变 background-size background-size 属性用于设置背景图像的尺寸。您可以指定绝对或相对单位,或者使用关键词来控制背景图像在元素背景区域中的大小。 .element {background-size: [length | percentage | cover | contain] | [length | percentage] [length | per…...
线性表——链式存储
单链表(有头结点) #include<stdio.h> #include<stdlib.h> //定义 typedef struct LNode{int data; //数据域 struct LNode *next; //指针域指向下一个结点,所以是 struct LNode类型 }LNode,*LinkList; //…...
VUE3和VUE2
VUE3和VUE2 上一篇文章中,我们对VUE3进行了一个初步的认识了解,本篇文章我们来进一步学习一下,顺便看一下VUE2的写法VUE3是否能做到兼容😀。 一、新建组件 我们在components中新建一个组件,名称为Peron,…...
mysql5.5版本安装过程
mysql是关系型数据库的管理系统 将安装包放在 c盘根目录 名称为mysql 在该路径下cmd进入命令执行窗口 出现此页面说明安装成功 需要修改配置文件内容 将my-medium.ini 复制粘贴并改名为 my.ini 并添加如下内容 改好之后在mysql目录下cmd进入命令执行窗口 切换到cd bin …...
工厂生产管理系统
为应对一些国内验厂,如大疆等,他们需要客户有自己的生产管理系统的,但实际很多公司是没有引入ERP这类的系统的,从而想开发一套简单的生产管理系统。 参考了网上一个比较古老的StorageMange项目,此项目用到DevExpress的…...
Atlas 200I DK A2安装MindSpore Ascend版本
一、参考资料 mindspore快速安装 二、重要说明 经过博主多次尝试多个版本,Atlas 200I DK A2无法安装MindSpore Ascend版本。 也有其他博主测试,也未尝成功,例如:【MindSpore易点通漫游世界】在Atlas 200I DK A2 (CANN6.2.RC2)…...
Go 生成UUID唯一标识
什么是UUID 通用唯一识别码(英语:Universally Unique Identifier,简称UUID)是一种软件建构的标准,亦为自由软件基金会组织在分散式计算环境领域的一部份。 UUID的目的,是让分散式系统中的所有元素&#x…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
