排序算法之【归并排序】
📙作者简介: 清水加冰,目前大二在读,正在学习C/C++、Python、操作系统、数据库等。
📘相关专栏:C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。
欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正!
✨每一次努力都是一种收获,每一次坚持都是一种成长✨
目录
前言
1. 归并排序
1.1 原理
2. 排序实现
2.1 递归
2.2 非递归
3. 复杂度
空间复杂度
时间复杂度
总结
前言
归并排序也是常用排序算法中较为重要的,对于新手来说较为复杂的排序算法,也是一个十分高效的排序算法。本篇文章我将带领大家深入理解归并排序。
1. 归并排序
归并排序是一种分治算法,它将一个大问题分解成多个小问题,然后将这些小问题的解合并起来得到最终的解。
1.1 原理
- 将待排序的数组分成多个子数组,分别对这些子数组进行归并排序。
- 对有序的两个子数组进行合并,合并后的数组是有序的。
归并排序核心步骤如下:
2. 排序实现
两两合并的前提是两个数组都必须有序,在归并排序中也存在使用递归和非递归的方法实现。
2.1 递归
我们先使用递归来实现归并,归并的过程中我们并不是在原数组中进行排序,我们需要额外创建一个等大的数组,将分解后排序过的数组放到新数组中,然后将新数组中排好的数据拷贝到原数组中。(每合并一次就拷贝一次)
首先我们肯定需要先开辟一个新的数组,然后是对数组进行分讲合并。
void MergrSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//调整排序接口free(tmp);
}
调整排序接口的实现,归并排序是对数组进行二等分,当分解到只有一个数据时开始合并。所以这里使用递归是非常合适的,先分解,当分解到最小,然后开始逐层返回合并(向下递归的过程为分解,递归返回的过程为合并)。
void _MergrSort(int* a, int* tmp, int begin, int end)
{if (end <= begin)return;int mid = (begin + end) / 2;_MergrSort(a, tmp, begin, mid);_MergrSort(a, tmp, mid + 1, end);//归并// ……}
接下来就是合并过程的实现。我们已知数组大小,对数组进行不断二分,每次归并时都是两两归并,这里我们需要记录一些两个数组的起始下标。然后遍历两数组,谁小就把数据尾插到新数组。
注意一个数组遍历结束,另一个数组没有结束的情况。
代码如下:
void _MergrSort(int* a, int* tmp, int begin, int end)
{if (end <= begin)return;int mid = (begin + end) / 2;_MergrSort(a, tmp, begin, mid);_MergrSort(a, tmp, mid + 1, end);//合并int begin1 = begin, end1 = mid;//记录两数组的起始下标int begin2 = mid + 1, end2 = end;int index = begin; //记录新数组数据的下标while (begin1 <= end1 && begin2 <= end2)//遍历数组,当一个数组遍历结束就结束{if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}//一共数组结束另一个数组没结束的情况while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}//归并一次,把数据拷贝回原数组一次memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));}
注意:记录新数组的下标index不要初始等于0,因为它将合并的数据放到到新数组时,开始的位置不一定是0,index是在函数内创建的变量出函数作用域无法保存,但是它开始的位置恰好就是当前合并范围中数组1的起始位置下标(begin1),所以index=begin;
2.2 非递归
使用递归需要消耗计算机的栈区,而栈区在计算机内存中空间很小,在多次调用函数的过程速度也没有同等条件下循环快(随着计算机的不断完善和优化它们之间差距其实也没那么大),考虑到空间和速度问题,我们很有必要学习一下非递归的实现方法。
非递归相对于递归来说有很多的坑,也更复杂一点。那我们实现非递归要怎么去设计?归并不和快排一样,它使用栈并不能模拟出归并的过程。
为什么?
例如上述的数组,我们在分的时候可以分为以下区间:
用栈来模拟实现逻辑如下:
在0~1和2~3区间数据各自归并后拷贝回原数组,下一步就需要将0~1和2~3这两个区间数据归并成一个数组,归并区间是0~3,但此时就再从栈里取,取出的是4~7这个区间。所以使用栈来模拟归并行不通。
那我们要怎么设计?我们来看一下它的归并划分:
那它的区间变化规律就可以这样写:
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
这里我们可以使用循环来跳区间,i的初始值为0,11归,跳到下一个归并区间开始位置需要跳2步;22归,跳到下一个归并区间开始位置需要跳4步;由此我们找到i的变化规律,i每次增加2倍gap。
void MergrSortNoneR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;for (int i = 0; i < n; i += gap * 2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int index = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}free(tmp);
}
这里的gap默认的是1,前边要求的gap是变化的,11归每次跳到下一个区间开始gap=1,22归每次跳到下一个区间开始gap=2,44归每次跳到下一个区间开始gap=4。gap每次扩大两倍。所以我们还需要再套一个循环:
void MergrSortNoneR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += gap * 2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int index = i;//归并//……}gap *= 2;}free(tmp);
}
到这里还并没有结束,这个代码还有一个大坑,我们使用的示例是8个数据,那如果是9个数据要怎么办?到第9个数据归并时发现没有和它相对于的归并区间,i如果在一次跳2倍gap就越界了。
注意: 我们在使用递归实现时使用的是除来二分区间,除到最后最小也是0,但使用i跳区间就不一样,它是乘,那就一定存在跳越界的情况。
所以在进行合并之前,我们需要判断一下是否越界,如果越界要及时修正。
for (int i = 0; i < n; i += gap * 2)
{int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int index = i;if (begin2 >= n)//只有一个完整数组{break;}if (end2 >= n)//有一个完整的区间,第二个归并区间超了就修正{end2 = n - 1;//n-1是数组最后元素下标}//归并//……}
非递归完整代码如下:
void MergrSortNoneR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += gap * 2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int index = i;if (begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}gap *= 2;}free(tmp);
}
3. 复杂度
说到排序那就一定要聊一聊它的复杂度。
空间复杂度
在进行排序时我们额外开辟了一个新的等大数组,由此看来它的空间复杂度是O(N)。
时间复杂度
在归并的过程中需要遍历每个子数组,然后重新排序,遍历子数组的时间复杂度是O(N),原数组二分成子数组,一共可以分logN个数组,所以它的时间复杂度就是O(N*logN)。
总结
以上便是本期全部内容,归并排序是一种高效的排序算法,在实际应用中也有很大的价值,是一种值得掌握的算法,希望本文对你有所帮助。最后,感谢阅读!
相关文章:

排序算法之【归并排序】
📙作者简介: 清水加冰,目前大二在读,正在学习C/C、Python、操作系统、数据库等。 📘相关专栏:C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 👍…...

Qt中QTimer定时器的用法
Qt中提供了两种定时器的方式一种是使用Qt中的事件处理函数,另一种就是Qt中的定时器类QTimer。 使用QTimer类,需要创建一个QTimer类对象,然后调用其start()方法开启定时器,此后QTimer对象就会周期性的发出timeout()信号。 1.QTimer…...
vue-组件定义注册使用
vue组件使用的步骤 定义组件注册组件使用组件 定义组件 Vue.extend(options) 其中options和new Vue(options)出入的options对象几乎一样,但是也有不同。 创建 el不用写—最终所有组件需要经过一个vm的管理,由vm的el决定服务哪个容器。 data必须写成函…...

斑馬打印機打印中文
创建项目 首先說一下,本文章是借鉴了其他大佬的文章,然后我记录一下的文章。 首先创建好一个.net framework的winform项目。 这里面主要用到两个库文件: Fnthex32.dll、LabelPrint.dll。 Fnthex32这个有8位参数和9位参数的,我这…...

(一)Apache log4net™ 手册 - 介绍
0、相关概念 Log4j 几乎每个大型应用程序都包含自己的日志记录或跟踪 API。根据这一规则,E.U. SEMPER 🌹项目决定编写自己的跟踪 API。那是在 1996 年初。经过无数次的增强、几个化身和大量的工作,API 已经发展成为 log4j —— 一个流行的 Ja…...

基于Java的民宿管理系统设计与实现(源码+lw+部署文档+讲解等)(民宿预约、民宿预订、民宿管理、酒店预约通用)
文章目录 前言具体实现截图论文参考详细视频演示代码参考源码获取 前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技…...

039:mapboxGL更换地图上的鼠标样式
第039个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中更换地图上的鼠标的样式。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共74行)相关API参考:专栏目标示例效果 配置方式 1)查看基础设置:htt…...

【云原生】K8S对外服务之Ingress
目录 一、Ingress 简介1.1Ingress 组成1.3Ingress-Nginx 工作原理 二、部署 nginx-ingress-controller2.1部署ingress-controller Pod及相关资源2.2ingress 暴露服务的方式2.3 采用方式二:DaemonSetHostNetworknodeSelector 三、采用方式二:DeploymentNo…...

分布式锁如何实现
分布式是现在的比较主流的技术,常常和微服务一起出现。那么对于多个实例之间,如何证分布式系统中多个进程或线程同步访问共享资源呢?我们其实一想到的就是锁,我们在java里边有 synchronized, 在python里有lock,但是这个…...

Mysql存储-EAV模式
Mysql存储-EAV模式 最近又又又搞一点新东西,要整合不同业务进行存储和查询,一波学习过后总结了一下可扩展性MAX的eav模式存储。 在eav这里的数据结构设计尤为关键,需要充分考虑你需要使用的字段、使用场景,当数据结构设计完成后便…...

全局变量报错:\Output\STM32.axf: Error: L6218E: Undefined symbol
全局变量报错: .\Output\STM32.axf: Error: L6218E: Undefined symbol key_num (referred from main.o). 这里只说全局变量哦,这是因为你在调用的.c文件里 把定义写在了函数里面,写函数外面就没事了 改为: .h的声明文件根本不用写…...

算法错题簿(持续更新)
自用算法错题簿,按算法与数据结构分类 python1、二维矩阵:记忆化搜索dp2、图论:DFS3、回溯:129612964、二叉树:贪心算法5、字符串:记忆化搜索6、01字符串反转:结论题7、二进制数:逆向…...

基于Springboot实现疫情网课管理系统项目【项目源码+论文说明】
基于Springboot实现疫情网课管理系统演示 摘要 随着科学技术的飞速发展,各行各业都在努力与现代先进技术接轨,通过科技手段提高自身的优势;对于疫情网课管理系统当然也不能排除在外,随着网络技术的不断成熟,带动了疫情…...

Linux文件与目录的增删改查
一、增 1、mkdir命令 作用: 创建一个新目录。 格式: mkdir [选项] 要创建的目录 常用参数: -p:创建目录结构中指定的每一个目录,如果目录不存在则创建,如果目录已存在也不会被覆盖。 用法示例&a…...

JVM的内存模型
一、JVM的内存模型 1.1、目标 内存模型是用来描述JVM内部的内存结构和内存管理的模型。它定义了JVM在运行Java程序时所需要的各种内存区域,以及每个内存区域的作用和特点。 1.2、结构划分 1.2.1、栈 每个线程在执行Java方法时会创建一个栈帧(Stack …...
数据采集项目之业务数据(三)
1. Maxwell框架 开发公司为Zendesk公司开源,用java编写的MySQL变更数据抓取软件。内部是通过监控MySQL的Binlog日志,并将变更数据以JSON格式发送到Kafka等流处理平台。 1.1 MySQL主从复制 主机每次变更数据都会生成对应的Binlog日志,从机可…...
vuedraggable影响点击事件的解决办法
在工作中有很多场景需要针对广告、商品、信息推广等进行一个排序,或者对展示的顺序做出调整,方便放用户第一眼看到自己感兴趣的信息,因此避免不了需要用到排序的插件,这里以vue为例子,采用的插件是vuedraggable,这个插件针对于排序的功能相对完善,官网地址:vuedraggable官网 但…...
Linux 中的 grep 命令
Linux 中的 grep 命令是一个强大的文本搜索工具,它允许用户在文件中查找指定的文本模式,并将匹配的行打印出来。grep 是“Global Regular Expression Print”的缩写,它使用正则表达式来进行文本搜索,因此具有强大的灵活性和功能。…...
阶段五-Day03-Ajax
一、JavaWeb中路径的说明 1. JavaWeb中的路径 在JavaWeb中, 路径分为相对路劲和绝对路径两种: 相对路径: ./ 表示当前目录 ../ 表示当前文件所在目录的上一级目录 绝对路径: 完整的路径名 2. 在JavaWeb中/的不同意义 /斜杠如果被浏览器解析,得到的是 协议本地ip端口号…...
EPOLL单线程版本 基于reactor 的 httpserver文件下载 支持多个客户端同时处理
之前写了一个httpserver的问价下载服务器 如果有多个客户端请求过来只能串行处理必须得等当前的操作完成之后才会处理 另外还存在 文件大的时候 会出错 处理不了 原因就是 sendfile是在一个while循环中处理的 当调用send失败返回-1之后 就 结束了 而一般来讲 se…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...

DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...

基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...