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

排序算法-----归并排序

目录

前言:

归并排序

1. 定义

2.算法过程讲解

2.1大致思路

2.2图解示例

拆分合成步骤

 ​编辑

相关动态图 

 3.代码实现(C语言)

4.算法分析

4.1时间复杂度

4.2空间复杂度

 4.3稳定性


前言:

        今天我们就开始学习新的排序算法----归并排序,说到归并排序,最重要的思想就是分而治之,先分后治。相较于前面所学过的排序算法,归并排序过程相对比较复杂,但是不要慌!我会详细讲解这个过程的!下面我们就一起来学习吧!

归并排序

1. 定义

        归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

2.算法过程讲解

2.1大致思路

已知一个数组arr[0,n-1],实现对这个数组进行拆分为arr[0,n/2]和arr[n/2+1,n-1]然后对这个数组进行进一步对半拆分,直到拆成每个分数组里面只有一个元素时,结束拆分;然后进入排序,按照拆分过程的路径进行排序合并,直到合并为一个数组的时候结束,最终得到的数组就是排序完成的数组。

归并排序是用分治思想,分治模式在每一层递归上有三个步骤:

  • 分解(Divide):将n个元素分成个含n/2个元素的子序列。
  • 解决(Conquer):用合并排序法对两个子序列递归的排序。
  • 合并(Combine):合并两个已排序的子序列已得到排序结果
2.2图解示例
拆分合成步骤

已知一个数组  [6,5,3,1,8,7,2,4],要求通过归并排序进行排序

第一步,依次拆分,直到每一个分数组剩下一个元素 ,如下所示:

                                                 6 5 3 1 8 7 2 4

第一次拆分                  6 5 3 1                           8 7 2 4

第二次拆分            6 5            3 1                8 7             2 4

第三次拆分        6        5       3        1        8        7       2        4

第二步,拆分完成之后,就进行排序        合并,如下所示:

                            6        5       3        1        8        7       2        4

第一次合并:          5 6               1 3              7 8              2 4      

第二次合并:                 1 3 5 6                            2 4 7 8

第三次合并:                              1 2 3 4 5 6 7 8

 以上步骤就完成了归并排序的过程了,演示图如下所示:

 动态图:

 
相关动态图 

 3.代码实现(C语言)

#include<stdio.h>
//归并排序
//合成排序
void merge(int* n,int *temp,int left,int mid,int rigth) {int l_pos = left;int r_pos = mid+1;int pos = left;//左右两部分数组进行比较合并while (l_pos <= mid && r_pos <= rigth) {if (n[l_pos] < n[r_pos])temp[pos++] = n[l_pos++];elsetemp[pos++] = n[r_pos++];}//如果左边还有多余的就直接补到后面去while (l_pos <= mid)temp[pos++] = n[l_pos++];//如果右边有多余的就直接补到后面去while (r_pos <= rigth)temp[pos++] = n[r_pos++];//这里只需要把原来的数组覆盖掉就行了while (left <= rigth) {n[left] = temp[left];left++;}}
//拆分与归并
void msort(int *n,int *temp,int left,int right) {if (left < right) {			int mid = (left + right) / 2;	//先拆分为两部分msort(n, temp, left, mid); //左边递归msort(n, temp, mid+1, right);//右半递归merge(n, temp, left, mid, right);	//拆分完成之后进行归并和排序}
}
//排序函数接口
void merge_sort(int* n, int length) {int* temp = (int*)malloc(sizeof(int) * length);//申请一个同样大小的辅助数组空间if (temp) {//如果申请成功msort(n, temp, 0, length-1);    //进入到排序free(temp);						//释放掉这个空间}else {printf("Space allocation failure");}
}int main() {int array[8] = { 25,24,6,65,11,43,22,51 };printf("排序前:");for (int i = 0; i < sizeof(array) / sizeof(int); i++) {printf("%d ", array[i]);}printf("\n排序后:");merge_sort(array, sizeof(array) / sizeof(int));for (int i = 0; i < sizeof(array) / sizeof(int); i++) {printf("%d ", array[i]);}
}
//排序前:25 24 6 65 11 43 22 51
//排序后:6 11 22 24 25 43 51 65

4.算法分析

4.1时间复杂度

        归并排序的速度仅次于快速排序,速度是相当快的。因为归并排序每次都是在相邻的数据中进行操作,所以归并排序时间复杂度为O(nlogn)

4.2空间复杂度

 你知道么,归并排序在任何情况下的时间复杂度永远都是 O(nlogn),是不是很奇怪呢?别急,凡事有得必有失,归并排序是通过牺牲空间的代价来实现减小时间复杂度的。上面的代码涉及到数据暂存空间的开辟,其开辟的空间数量最大也不会超过n,所以空间复杂度为O(n)

 4.3稳定性

归并排序是稳定的排序算法,因为无论是在排序拆解过程中还是在归并过程中都没有改变相同元素的相对位置,所以是稳定的。

 好了,以上就是今天的全部内容了,你们学会了吗?我们下一期再见!

相关文章:

排序算法-----归并排序

目录 前言&#xff1a; 归并排序 1. 定义 2.算法过程讲解 2.1大致思路 2.2图解示例 拆分合成步骤 ​编辑 相关动态图 3.代码实现&#xff08;C语言&#xff09; 4.算法分析 4.1时间复杂度 4.2空间复杂度 4.3稳定性 前言&#xff1a; 今天我们就开始学习新的排序算法…...

docker 配置 gpu版pytorch环境--部署缺陷检测--Anomalib

目录 一、docker 配置 gpu版pyhorch环境1、显卡驱动、cuda版本、pytorch cuda版本三者对应2、拉取镜像 二、部署Anomalib1、下载Anomalib2、创建容器并且运行3、安装Anomalib进入项目路径安装依赖测试&#xff1a; 一、docker 配置 gpu版pyhorch环境 1、显卡驱动、cuda版本、p…...

为什么定时发朋友圈会更有效呢?

这是因为在同一时段 发送的好友朋友圈 无法有效分散用户的注意力 导致曝光度难以提升 而通过推广定时发朋友圈 可根据自己的粉丝活跃度 设置发圈时间 让每一条朋友圈都能高效 传递到更多的好友手中 这样&#xff0c;曝光度自然而然地就大大提升了&#xff01; 1.多个号…...

【跟小嘉学 PHP 程序设计】一、PHP 开发环境搭建

系列文章目录 【跟小嘉学 PHP 程序设计】一、PHP 开发环境搭建 文章目录 系列文章目录@[TOC](文章目录)前言一、PHP介绍二、Centos 安装 PHP2.1、安装并启动 Nginx2.2、安装并启动 mariadb2.3、安装 rh-php2.4、添加 Nginx 配置2.5、Nginx 服务三、使用 Docker 为 PHP 部署开发…...

【zookeeper】zk选举、使用与三种节点简介,以及基于redis分布式锁的缺点的讨论

这里我准备了4台虚拟机&#xff0c;从node1到node4&#xff0c;其myid也从1到4. 一&#xff0c;zk server的启动和选举 zk需要至少启动3台Server&#xff0c;按照配置的myid&#xff0c;选举出参与选举的myid最大的server为Leader。&#xff08;与redis的master、slave不同&a…...

Unity截图生成图片 图片生成器 一键生成图片

使用Unity编辑器扩展技术实现快速截图功能 效果&#xff1a; 里面没有什么太难的技术&#xff0c;直接上源码吧 注意&#xff01;代码需要放在Editor文件下才能正常运行 using System; using UnityEditor; using UnityEngine;[ExecuteInEditMode] public class Screenshot …...

Matlab图像处理-区域特征

凹凸性 设P是图像子集S中的点&#xff0c;若通过的每条直线只与S相交一次&#xff0c;则称S为发自P的星形&#xff0c;也就是站在P点能看到S的所有点。 满足下列条件之一&#xff0c;称此为凸状的&#xff1a; 1.从S中每点看&#xff0c;S都是星形的&#xff1b; 2.对S中任…...

golang 自动生成文件头

安装koroFileHeader控件 打开首选项&#xff0c;进入设置&#xff0c;配置文件头信息"fileheader.customMade": {"Author": "lmy","Date": "Do not edit", // 文件创建时间(不变)// 文件最后编辑者"LastEditors"…...

Excel中的宏、VBA

一、宏是什么&#xff1f; EXCEL MACRO 是一种记录和播放工具&#xff0c;它仅记录您的 Excel 步骤&#xff0c;并且宏将根据需要播放任意多次。 VBA 宏可自动执行重复任务&#xff0c;从而节省了时间。 这是一段可在 Excel 环境中运行的编程代码&#xff0c;但您无需成为编码…...

2023华为杯数学建模研赛思路分享——最全版本A题深度解析

问题回顾&#xff1a; WLAN网络信道接入机制建模 1. 背景 无线局域网&#xff08;WLAN, wireless local area network&#xff09;也即Wi-Fi广泛使用&#xff0c;提供低成本、高吞吐和便利的无线通信服务。基本服务集&#xff08;BSS, basic service set&#xff09;是WLAN的…...

【校招VIP】测试方案之测试需求分析

考点介绍&#xff1a; 需求分析就是要弄清楚用户需要的是什么功能&#xff0c;用户会怎样使用系统。这样我们测试的时候才能更加清楚的知道系统该怎么样运行&#xff0c;才能更好的设计测试用例&#xff0c;才能更好的测试。 测试方案之测试需求分析-相关题目及解析内容可点击…...

滚珠螺母的清洁方式

滚珠螺母是一种通过滚珠与螺杆进行螺旋运动转换的机械零件&#xff0c;主要用于控制螺杆的运动轨迹和方向&#xff0c;把原来的滑动摩擦利用滚珠的滚动变成滚动摩擦&#xff0c;因此滚珠螺母的摩擦系数大大降低&#xff0c;从而提高了传动效率&#xff0c;要想滚珠螺母达到预期…...

leetcode做题笔记148. 排序链表

给你链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 思路一&#xff1a;归并排序 c语言解法 struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) {struct ListNode* dummyHead malloc(sizeof(struct ListNode));dummyHead…...

多线程学习

并发&#xff1a;交替运行 并行&#xff1a;一起运行 多线程实现方式 继承Thread类 ①自己定义一个类继承Thread public class MyThread extends Thread{public void run(){}} ②重写run方法 public class MyThread extends Thread{public void run(){"重写的内容&…...

软件测试/测试开发丨ChatGPT在测试计划中的应用策略

点此获取更多相关资料 简介 测试计划是指描述了要进行的测试活动的范围、方法、资源和进度的文档。它主要包括测试项、被测特性、测试任务和风险控制等。 所以在使用ChatGPT输出结果之前&#xff0c;我们需要先将文档的内容框架梳理好&#xff0c;以及将内容范围划定好&…...

链表oj3(Leetcode)——相交链表;环形链表

一&#xff0c;相交链表 相交链表&#xff08;Leetcode&#xff09; 1.1分析 看到这个我们首先想到的就是一个一个比较他们的值有相等的就是交点&#xff0c;但是如果a1和b2的值就相等呢&#xff1f;所以这个思路不行&#xff0c;第二种就是依次比较链表&#xff0c;但是这…...

nginx反向代理

nginx反向代理8.反向代理8.1 实现http反向代理8.1.1 反向代理配置参数8.1.2 反向代理单台web服务器8.1.2.1 端口号后加"/"8.1.2.2 端口号后不加"/" 8.1.3指定location 实现反向代理,动静分离8.1.4 反向代理实例&#xff1a;缓存功能8.1.4.1 举例 8.1.5 实现…...

基于eBPF的安卓逆向辅助工具——stackplz

前言 stackplz是一款基于eBPF技术实现的追踪工具&#xff0c;目的是辅助安卓native逆向&#xff0c;仅支持64位进程&#xff0c;主要功能如下&#xff1a; hardware breakpoint 基于pref_event实现的硬件断点功能&#xff0c;在断点处可读取寄存器信息&#xff0c;不会被用户…...

十大排序——4.堆排序

前面我们讲了堆&#xff0c;现在我们来看一下队排序。 堆排序的步骤&#xff1a; 首先将一个无序数组建立成一个大顶堆然后&#xff0c;将堆顶的元素和堆低的元素进行交换&#xff08;即将最大的元素交换的到堆底&#xff09;&#xff0c;缩小并下潜调整堆重复上一步&#xf…...

独辟蹊径”之动态切换进程代理IP

前言 项目中遇到这样一个需求&#xff0c;需要动态切换指定进程Sockets5代理IP&#xff0c;目前了解到可通过编写驱动拦截或者劫持LSP实现&#xff0c;LSP劫持不太稳定&#xff0c;驱动无疑是相对较好的解决方案&#xff0c;奈何水平不足便有了这"蹊径"。 初步尝试…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...