【数据结构与算法】十大经典排序算法-归并排序

🌟个人博客:www.hellocode.top
🏰Java知识导航:Java-Navigate
🔥CSDN:HelloCode.
🌞知乎:HelloCode
🌴掘金:HelloCode
⚡如有问题,欢迎指正,一起学习~~


当谈到高效的排序算法时,归并排序是一个备受推崇的选择。归并排序是一种分治算法,它将一个大问题分解成若干个小问题,然后逐个解决这些小问题,并将它们合并成一个整体的解。

基本思想

这里采用五分钟学算法大佬的图解,十分清晰

  1. 分解阶段: 将待排序数组分成两个相等或近似相等的子数组,不断将问题规模缩小。
  2. 解决阶段: 递归地对两个子数组进行排序,直到子数组的长度为1(即已有序)。
  3. 合并阶段: 将排好序的子数组合并成一个有序的数组,这是归并排序的核心操作。

三个阶段,涉及到递归就比较难理解(个人感觉),最好配合动画好好理解理解。主要就是分解和归并(将大问题分解为小问题,再通过归并过程合并并排序)

代码实现

每次随便写数组挺麻烦的,后续就都使用我写的工具类来生成随机数组了~

归并排序相对难理解一些,主要涉及到分解和归并,将待排序数组一个个拆分,直到拆分为1个1组(无需排序),接下来就是自底向上逐个合并,在合并的同时进行排序操作,最终合并好的就是有序的数组了

/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月15日 19:33*/
public class MergeSort {public static void main(String[] args) {// 生成容量为15的由100以内随机数构成的int数组(用到了自己写的一个工具类)int[] arr = ArrayUtil.randomIntArray(15, 100);System.out.println("原数组:" + Arrays.toString(arr));mergeSort(arr);System.out.println("排序后:" + Arrays.toString(arr));}private static void mergeSort(int[] arr) {if (arr == null || arr.length <= 1) {return; // 数组为空或只有一个元素,无需排序}// 创建临时数组(避免多次创建)int[] temp = new int[arr.length];// 递归入口sort(arr, temp, 0, arr.length - 1);}// 拆分private static void sort(int[] arr, int[] temp, int left, int right) {// 递归出口if (left >= right) {return;}// 记录中间值(左边数组的末尾,+1为右边数组的起始)int mid = left + ((right - left) >> 1);// 开始拆分sort(arr, temp, left, mid);sort(arr, temp, mid + 1, right);// 归并merge(arr, temp, left, mid, right);}// 归并(排序)private static void merge(int[] arr, int[] temp, int left, int mid, int right) {// 记录临时数组索引int p = left;// 左半边起始索引int i = left;// 右半边起始索引int j = mid + 1;// 开始归并// 两边都还有的情况while(i <= mid && j <= right){if(arr[i] <= arr[j]){temp[p++] = arr[i++];}else{temp[p++] = arr[j++];}}// 左边还有剩余的情况(直接加到临时数组末尾)while(i <= mid){temp[p++] = arr[i++];}// 右边还有剩余的情况(直接加到临时数组末尾)while(j <= right){temp[p++] = arr[j++];}// 将临时数组拷贝回原数组for(int k = left; k <= right; k++){arr[k] = temp[k];}}
}

测试:

原数组:[83, 49, 19, 75, 26, 64, 59, 60, 11, 97, 36, 41, 17, 31, 69]
排序后:[11, 17, 19, 26, 31, 36, 41, 49, 59, 60, 64, 69, 75, 83, 97]

生成随机数组的工具类:

/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月13日 20:01*/
public class ArrayUtil {private static final Random RANDOM = new Random();public static int[] randomIntArray(int capacity,int max){// 创建capacity大小的数组(1~max)int[] res = new int[capacity];for(int i = 0; i < capacity; i++){res[i] = RANDOM.nextInt(max) + 1;}return res;}
}

优化

归并排序本身是一个稳定且效率较高的排序算法,但还是有一些优化方法可以进一步提升性能:

  1. 插入排序优化: 对于小规模子数组,使用插入排序可以提高性能。当子数组长度小于一定阈值时,切换到插入排序可以减少递归调用开销。
  2. 自底向上归并: 在归并阶段,可以使用自底向上的方法,避免递归调用,从而减少栈空间的使用。
  3. 优化合并操作: 在合并阶段,如果左子数组的最大元素小于右子数组的最小元素,可以直接跳过合并操作,因为两个子数组已经有序。

总结

优点

  1. 归并排序稳定且适用于各种数据类型。
  2. 具有稳定的时间复杂度O(n log n),适用于大规模数据排序。
  3. 分治思想使其易于理解和实现,同时也为优化提供了空间。

缺点

  1. 归并排序需要额外的存储空间来存储临时数组,空间复杂度较高。
  2. 在小规模数据排序时,性能稍逊于快速排序。

复杂度

  • 时间复杂度:平均情况、最好情况和最坏情况下的时间复杂度均为O(n log n)。
  • 空间复杂度:空间复杂度为O(n),需要额外的存储空间来存储临时数组。

使用场景

  • 归并排序适用于需要稳定排序的场景,对性能有一定要求。
  • 特别适合用于外部排序,如在磁盘上对大文件进行排序。

通过分治思想,归并排序将排序问题分解为小问题,并通过合并操作将它们逐步解决,从而实现高效且稳定的排序。这使得归并排序成为计算机科学中重要的算法之一。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/96787.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

RocketMQ 5.0 架构解析:如何基于云原生架构支撑多元化场景

作者&#xff1a;隆基 本文将从技术角度了解 RocketMQ 的云原生架构&#xff0c;了解 RocketMQ 如何基于一套统一的架构支撑多元化的场景。 文章主要包含三部分内容。首先介绍 RocketMQ 5.0 的核心概念和架构概览&#xff1b;然后从集群角度出发&#xff0c;从宏观视角学习 R…

改进YOLO系列:4.添加ACmix注意力机制

添加ACmix注意力机制 1. ACmix注意力机制论文2. ACmix注意力机制原理3. ACmix注意力机制的配置3.1common.py配置3.2yolo.py配置3.3yaml文件配置1. ACmix注意力机制论文 论文题目:On the Integration of Self-Attention and Convolution 论文链接:On the Integration…

【ROS】话题通信--从理论介绍到模型实现(C++)

1.简单介绍 话题通信是ROS中使用频率最高的一种通信模式&#xff0c;话题通信是基于发布订阅模式的&#xff0c;也即:一个节点发布消息&#xff0c;另一个节点订阅该消息。像雷达、摄像头、GPS… 等等一些传感器数据的采集&#xff0c;也都是使用了话题通信&#xff0c;换言之…

相机的位姿在地固坐标系ECEF和ENU坐标系的转换

在地球科学和导航领域&#xff0c;通常使用地心地固坐标系&#xff08;ECEF&#xff0c;Earth-Centered, Earth-Fixed&#xff09;和东北天坐标系&#xff08;ENU&#xff0c;East-North-Up&#xff09;来描述地球上的位置和姿态。如下图所示&#xff1a; ​地心地固坐标ecef和…

Python标准库-追踪异常,定位问题-traceback

在日常的编程过程中&#xff0c;我们经常会遇到各种错误和异常。而当程序发生异常时&#xff0c;了解如何有效地追踪异常信息并定位问题&#xff0c;是每个开发者必备的技能之一。 Python 提供了一个强大的工具&#xff0c;称为 Traceback&#xff0c;它可以帮助我们跟踪异常的…

java 工程管理系统源码+项目说明+功能描述+前后端分离 + 二次开发 em

Java版工程项目管理系统 Spring CloudSpring BootMybatisVueElementUI前后端分离 功能清单如下&#xff1a; 首页 工作台&#xff1a;待办工作、消息通知、预警信息&#xff0c;点击可进入相应的列表 项目进度图表&#xff1a;选择&#xff08;总体或单个&#xff09;项目显…

Tomcat的部署及优化(多实例和动静分离)

目录 绪论 1、tomact 1.1 核心组件 1.2 什么是 servlet 1.3 什么是 JSP? 1.4 Tomcat 功能组件结构 1.5 Tomcat 请求过程 2、Tomcat 服务部署 2.1 tomcat自身优化&#xff1a; 2.2 内核优化 2.3 jvm 2.3.1 jvm配置 2.3.2 Tomcat配置JVM参数 2.3.3 jvm优化 3、tom…

SpringBoot案例-员工管理-新增员工

查看页面原型&#xff0c;明确需求 页面原型 需求 阅读接口文档 接口文档链接如下&#xff1a; 【腾讯文档】SpringBoot案例所需文档 https://docs.qq.com/doc/DUkRiTWVaUmFVck9N 思路分析 阅读需求文档后可知&#xff0c;前端发送请求的同时&#xff0c;将前端请求参数以…

画质提升+带宽优化,小红书音视频团队端云结合超分落地实践

随着视频业务和短视频播放规模不断增长&#xff0c;小红书一直致力于研究&#xff1a;如何在保证提升用户体验质量的同时降低视频带宽成本&#xff1f; 在近日结束的音视频技术大会「LiveVideoStackCon 2023」上海站中&#xff0c;小红书音视频架构视频图像处理算法负责人剑寒向…

使用el-tree实现自定义树结构样式

实现效果: 直接上代码: <template><div><div class"tops"><el-tree :default-expanded-keys"[1]" ref"myTree" :data"data" :props"defaultProps" node-click"handleNodeClick" highlight…

IDEA两种方法修改生成的jar包名字

方法一&#xff1a; 直接修改pom文件中的如下部分 <artifactId>excelreport</artifactId> <version>0.0.1-SNAPSHOT</version> <name>excelreport</name> <description>excelreport</description> 修改完成后&#xff0c;点…

LVS+Keepalived

Keepalived概述&#xff1a; keepalived软件 就是通过vrrp协议实现高可用功能 vrrp通信原理&#xff1a; vrrp就是虚拟路由冗余协议&#xff0c;它的出现就是为了解决静态路由的单点故障vrrp是通过一种竞选的一种协议机制将路由交给某台vrrp路由器vrrp用ip多播的方式【多播地…

2023+HuggingGPT: Solving AI Tasks with ChatGPT and itsFriends in Hugging Face

摘要&#xff1a; 语言是llm(例如ChatGPT)连接众多AI模型(例如hugs Face)的接口&#xff0c;用于解决复杂的AI任务。在这个概念中&#xff0c;llms作为一个控制器&#xff0c;管理和组织专家模型的合作。LLM首先根据用户请求规划任务列表&#xff0c;然后为每个任务分配专家模…

LLaMA模型泄露 Meta成最大受益者

一份被意外泄露的谷歌内部文件&#xff0c;将Meta的LLaMA大模型“非故意开源”事件再次推到大众面前。“泄密文件”的作者据悉是谷歌内部的一位研究员&#xff0c;他大胆指出&#xff0c;开源力量正在填平OpenAI与谷歌等大模型巨头们数年来筑起的护城河&#xff0c;而最大的受益…

如何使用Kali Linux进行渗透测试?

1. 渗透测试简介 渗透测试是通过模拟恶意攻击&#xff0c;评估系统、应用或网络的安全性的过程。Kali Linux为渗透测试人员提供了丰富的工具和资源&#xff0c;用于发现漏洞、弱点和安全风险。 2. 使用Kali Linux进行渗透测试的步骤 以下是使用Kali Linux进行渗透测试的基本…

万宾燃气管网监测解决方案,守护城市生命线安全

方案背景 城市燃气管网作为连接天然气长输管线与天然气用户的桥梁&#xff0c;担负着向企业和居民用户直接供气的重要职责。随着城市燃气需求的急剧增加&#xff0c;城市燃气管网规模日趋庞大&#xff0c;安全隐患和风险也随之增加。目前&#xff0c;我国燃气管网的运行仍存在…

3D沉浸式旅游网站开发案例复盘【Three.js】

Plongez dans Lyon网站终于上线了。 我们与 Danka 团队和 Nico Icecream 共同努力&#xff0c;打造了一个令我们特别自豪的流畅的沉浸式网站。 这个网站是专为 ONLYON Tourism 和会议而建&#xff0c;旨在展示里昂最具标志性的活动场所。观看简短的介绍视频后&#xff0c;用户…

react之react-redux的介绍、基本使用、获取状态、分发动作、数据流、reducer的分离与合并等

react之react-redux的介绍、基本使用、获取状态、分发动作、数据流、reducer的分离与合并等 一、react-redux介绍二、React-Redux-基本使用三、获取状态useSelector四、分发动作useDispatch五、 Redux 数据流六、代码结构七、ActionType的使用八、Reducer的分离与合并九、购物挣…

【数据结构】二叉树篇|超清晰图解和详解:二叉树的最近公共祖先

博主简介&#xff1a;努力学习的22级计算机科学与技术本科生一枚&#x1f338;博主主页&#xff1a; 是瑶瑶子啦每日一言&#x1f33c;: 你不能要求一片海洋&#xff0c;没有风暴&#xff0c;那不是海洋&#xff0c;是泥塘——毕淑敏 目录 一、题目二、题解三、代码 一、题目 …

【宝藏系列】一文讲透C语言数组与指针的关系

【宝藏系列】嵌入式 C 语言代码优化技巧【超详细版】 文章目录 【宝藏系列】嵌入式 C 语言代码优化技巧【超详细版】&#x1f468;‍&#x1f3eb;前言1️⃣指针1️⃣1️⃣指针的操作1️⃣2️⃣关于指针定义的争议1️⃣3️⃣对教材错误写法的小看法 2️⃣指针和数组的区别2️⃣…