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

排序算法-归并排序

属性

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

        归并排序总结

        1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。

        2. 时间复杂度:O(N*logN)

        3. 空间复杂度:O(N)

        4. 稳定性:稳定

代码及注释(递归实现)

    //mergeSort是归并排序提供使用的方法public static void mergeSort(int[]arr){//用mergeSortChild进行递归排序mergeSortChild(arr,0,arr.length-1);}private static void mergeSortChild(int[]arr,int left,int right){//出递归if(left>=right){return;}//先计算出要排序数据的中间位置int mid=(left+right)/2;//先分别归并排序左边和右边的数据,排序好以后再将左边和右边的数据合并mergeSortChild(arr,left,mid);mergeSortChild(arr,mid+1,right);merge(arr,left,right);}private static void merge(int[]arr,int left,int right){int mid=(left+right)/2;//left和right范围的数据分为了两个部分//用s1,e1表示第一部分的数据范围,s2,e2表示第二部分的数据范围//两个部分的数据分别是排序好了的,要将两个部分的数据进行合并int s1=left;int e1=mid;int s2=mid+1;int e2=right;//定义辅助数组help来帮助合并int[]help=new int[right-left+1];//放数据的时候有以下的几种情况//1.两个部分的数据还没有哪个部分全放到help数组中int k=0;    //k是用于指向help数组的下标while (s1<=e1&&s2<=e2){//当s1下标的数据比s2下标的小时,s1下标的数据就先放到help数组中if(arr[s1]<arr[s2]){help[k++]=arr[s1++];}else {help[k++]=arr[s2++];}}//2.s1>e1 第一部分的数据都放到了help数组中//直接将第二部分的数据全放到help数组中while (s2<=e2){help[k++]=arr[s2++];}//3.s2>e1 第二部分的数据都放到了help数组中//直接将第一部分的数据全放到help数组中while (s1<=e1){help[k++]=arr[s1++];}//此时两个部分的数据都放到了help数组中//将数组中对应部分的数据改为help数组中的数据(help数组中的数据是合并好了的)for(int i=left,j=0;i<=right;i++,j++){arr[i]=help[j];}}

代码及注释(非递归实现)
 

 //归并排序---非递归public static void mergeSortNo(int[] array){//一个数据为一组int gap=1;while (gap<array.length){for(int i=0;i<array.length;i+=2*gap){int left=i;int mid=left+gap-1;int right=mid+gap;merge(array,left,mid,right);}gap=gap*2;}} //合并private static void merge(int[] array,int left,int mid,int right){int s1=left;int e1=mid;int s2=mid+1;int e2=right;//定义辅助数组int[]help=new int[right-left+1];int k=0;//两组数据都没放完while (s1<=e1&&s2<=e2){if(array[s1]<array[s2]){help[k++]=array[s1++];}else {help[k++]=array[s2++];}}//当有一组中的数据放完while (s1<=e1){help[k++]=array[s1++];}while (s2<=e2){help[k++]=array[s2++];}//将合并好的数据返回给数组arrayfor (int i=0;i<help.length;i++){array[left+i]=help[i];}}

相关文章:

排序算法-归并排序

属性 归并排序&#xff08;MERGE-SORT&#xff09;是建立在归并操作上的一种有效的排序算法,该算法是采用分治法&#xff08;Divide and Conquer&#xff09;的一个非常典型的应用。将已有序的子序列合并&#xff0c;得到完全有序的序列&#xff1b;即先使每个子序列有序&#…...

vue3 整合 springboot 打完整jar包

前端 .env.developmen VITE_APP_BASE_URL/api.env.production VITE_APP_BASE_URL/axios 配置 axios.defaults.baseURL import.meta.env.VITE_APP_BASE_URLpackage.json "scripts": {"dev": "vite --mode development","build": &…...

依赖倒转原则是什么?

依赖倒转原则&#xff08;Dependency Inversion Principle&#xff09;是面向对象设计中的另一个基本原则&#xff0c;它是由Robert C. Martin提出的&#xff0c;它的中心思想是面向接口编程&#xff0c;该原则指出高层模块不应该依赖于低层模块&#xff0c;两者都应该依赖于抽…...

什么是GPT与MBR

GPT&#xff08;GUID Partition Table&#xff09;和MBR&#xff08;Master Boot Record&#xff09;是两种不同的磁盘分区表格式。 MBR是一种较早的磁盘分区表格式&#xff0c;它使用512字节的扇区作为存储空间。MBR分区表可以定义最多4个主分区&#xff0c;每个主分区都可以…...

前后端开发接口联调对接参数

前言 一个完整的互联网系统项目,需要前后端配合,进行上线,针对前端开发者,现在互联网主流的项目都是前后端分离 也就是后端负责提供数据接口,前端负责UI界面数据渲染 凡是在前台数据展示与用户交互的,都是由前端来实现的,而数据来源是由后台服务提供的 在浏览器c端能够发送后端…...

定时任务框架-xxljob

1.定时任务 spring传统的定时任务Scheduled&#xff0c;但是这样存在这一些问题 &#xff1a; 做集群任务的重复执行问题 cron表达式定义在代码之中&#xff0c;修改不方便 定时任务失败了&#xff0c;无法重试也没有统计 如果任务量过大&#xff0c;不能有效的分片执行 …...

idea项目配置三大步

场景&#xff1a; 使用 idea 打开一个新项目的时候&#xff0c;想让项目迅速跑起来&#xff0c; 其实只需要下面简单三步&#xff1a; 1. 首先&#xff0c;配maven 2. 其次&#xff0c;配置 jdk 这里配置 project 就行了&#xff0c;不用管Modules中的配置。 3. 最后&#…...

学会SpringMVC之自定义注解各种场景应用,提高开发效率及代码质量

目录 一、简介 ( 1 ) 是什么 ( 2 ) 分类 ( 3 ) 作用 二、自定义注解 ( 1 ) 如何自定义注解 ( 2 ) 场景演示 场景一&#xff08;获取类与方法上的注解值&#xff09; 场景二&#xff08; 获取类属性上的注解属性值 &#xff09; 场景三&#xff08; 获取参数修…...

步态识别常见模块解读及代码实现:基于OpenGait框架

步态识别常见模块解读及代码实现&#xff1a;基于OpenGait框架 最近在看步态识别相关论文&#xff0c;但是因为记忆力下降的原因&#xff0c;老是忘记一些内容。因此记录下来方便以后查阅&#xff0c;仅供自己学习参考&#xff0c;没有背景知识和论文介绍。 目录 步态识别常见…...

前端八股文之“闭包”

一、定义 一句话概括闭包&#xff1a;能够访问函数内部变量的函数与这个变量的组合构成了闭包结构。如下代码 function fuc1(){let num 999return function fuc2(){console.log(num)}}fuc1()(); 如代码所示&#xff0c;fuc2和父级变量num构成了一个闭包环境。 二、原理 子…...

数据可视化:掌握数据领域的万金油技能

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ 🐴作者:秋无之地 🐴简介:CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作,主要擅长领域有:爬虫、后端、大数据开发、数据分析等。 🐴欢迎小伙伴们点赞👍🏻、收藏⭐️、…...

Apache Kafka 基于 S3 的数据导出、导入、备份、还原、迁移方案

在系统升级或迁移时&#xff0c;用户常常需要将一个 Kafka 集群中的数据导出&#xff08;备份&#xff09;&#xff0c;然后在新集群或另一个集群中再将数据导入&#xff08;还原&#xff09;。通常&#xff0c;Kafka集群间的数据复制和同步多采用 Kafka MirrorMaker&#xff0…...

事务管理AOP

事务管理 事务回顾 概念&#xff1a;事务是一组操作的集合&#xff0c;它是一个不可分割的工作单位&#xff0c;这些操作要么同时成功&#xff0c;要么同时失败 操作&#xff1a; 开启事务&#xff1a;一组操作开始前&#xff0c;开启事务&#xff0d;start transaction/be…...

Java从Tif中抽取最大的那张图进行裁剪成x*y份

之前我有一篇帖子《kfb格式文件转jpg格式》讲述到 kfb > tif > jpg&#xff0c;但是针对于超大tif中的大图是无法顺利提取的&#xff0c;就算是能顺利提取&#xff0c;试想一下&#xff0c;2G的tif文件&#xff0c;如果能提取处理最大的那张图&#xff0c;并且在不压缩的…...

人工智能AI界的龙头企业,炸裂的“英伟达”时代能走多远

原创 | 文 BFT机器人 1、AI芯片的竞争格局已趋白热化 尽管各类具有不同功能和定位的AI芯片在一定程度上可实现互补&#xff0c;但同时也在机遇与挑战并存中持续调整定位。在AI训练端&#xff0c;英伟达的GPU凭着高算力的门槛&#xff0c;一直都是训练端的首选。 只有少数芯片能…...

【实战】H5 页面同时适配 PC 移动端 —— 旋转横屏

文章目录 一、场景二、方案三、书单推荐01 《深入实践Kotlin元编程》02 《Spring Boot学习指南》03 《Kotlin编程实战》 一、场景 一个做数据监控的单页面&#xff0c;页面主要内容是一个整体必须是宽屏才能正常展示&#xff0c;这时就不能用传统的适配方案了&#xff0c;需要…...

使用凌鲨进行聚合搜索

作为研发人员&#xff0c;我们经常需要在多个来源之间查找信息&#xff0c;以便进行研发工作。除了常用的搜索引擎如百度和必应之外&#xff0c;我们还需要查阅各种代码文档和依赖包等资源。这些资源通常分散在各个网站和文档库中&#xff0c;需要花费一定的时间和精力才能找到…...

程序设计之——手把手教你如何从Excel文件中读取学生信息

在当今信息化时代&#xff0c;计算机技术已经深入到各个领域&#xff0c;而程序设计则成为推动信息化建设的关键技术之一。在众多领域中&#xff0c;学生信息管理系统无疑是其中一个重要的应用。本文将从学生信息管理系统的开发入手&#xff0c;探讨开如何高效且保证质量的完成…...

Docker容器化技术(从零学会Docker)

文章目录 前言一、初识Docker1.初识Docker-Docker概述2.初识Docker-安装Docker3.初识Docker-Docker架构4.初识Docker-配置镜像加速器 二、Docker命令1.Docker命令-服务相关命令2.Docker命令-镜像相关命令3.Docker命令-容器相关命令 三、Docker容器的数据卷1.Docker容器数据卷-数…...

【新版】系统架构设计师 - 案例分析 - 总览

个人总结&#xff0c;仅供参考&#xff0c;欢迎加好友一起讨论 架构 - 案例分析 - 总览 新旧大纲对应 旧版新版系统规划软件架构设计设计模式系统设计系统建模分布式系统设计嵌入式系统设计系统的可靠性分析与设计系统的安全性和保密性设计系统计划信息系统架构的设计理论和实…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...