Java的归并排序
不爱生姜不吃醋⭐️⭐️⭐️
如果本文有什么错误的话欢迎在评论区中指正
与其明天开始,不如现在行动!
文章目录
- 🌴前言
- 🌴一.归并排序
- 1.概念
- 2.时间复杂度
- 3.代码实现
- 🌴二、小和问题
- 1.概念
- 2.举例
- 3.代码实现
- 🌴三、逆序对问题
- 1. 概念
- 2. 举例
- 3.代码实现
- 🌴总结
🌴前言
归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。
🌴一.归并排序
1.概念
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置
第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
2.时间复杂度
O(n log n)
3.代码实现
public class Example1 {public static void main(String[] args) {int[] arr = {1, 5, 9, 3, 4, 6, 2, 7, 99, 2, 3, 7, 9, 5, 4,76};process(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}private static void process(int[] arr, int L, int R) {if (L == R) {return;}int mid = L + ((R - L) >> 1);process(arr, L, mid);process(arr, mid + 1, R);merge(arr, L, mid, R);}private static void merge(int[] arr, int L, int M, int R) {int[] temp = new int[R - L + 1];int i = 0;int p1 = L;int p2 = M + 1;while (p1 <= M && p2 <= R) {temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= M){temp[i++]=arr[p1++];}while (p2 <= R){temp[i++] = arr[p2++];}for (int j = 0; j < temp.length; j++) {arr[L+j] = temp[j];}}
}
🌴二、小和问题
1.概念
在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。
2.举例
数组【1,3,4,2,5】中
1
左边比1
小的数,没有
3
左边比3
小的数:1
4
左边比4
小的数:1
、3
2
左边比2
小的数:1
5
左边比5
小的数:1
、3
、4
、2
所以,小和为:1+1+3+1+1+3+4+2=16
3.代码实现
public class Example2 {public static void main(String[] args) {int[] arr = {1, 3, 4, 2, 5};System.out.println(process(arr, 0, arr.length - 1));}private static int process(int[] arr, int l, int r) {if (l == r) {return 0;}int mid = l + ((r - l) >> 1);int leftSum = process(arr, l, mid);int rightSum = process(arr, mid + 1, r);return leftSum + rightSum + merge(arr, l, mid, r);}private static int merge(int[] arr, int l, int mid, int r) {int[] temp = new int[r - l + 1];int i = 0;int p1 = l;int p2 = mid + 1;int sum = 0;while (p1 <= mid && p2 <= r) {sum += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= mid) {temp[i++] = arr[p1++];}while (p2 <= r) {temp[i++] = arr[p2++];}for (int j = 0; j < temp.length; j++) {arr[l + j] = temp[j];}return sum;}
}
🌴三、逆序对问题
1. 概念
在一个数组中,左边的数如果比右边的数大,则这两个数构成一个逆序对。
2. 举例
在数组【3,2,4,5,0】中
比3
小的:2
、0
比2
小的:0
比4
小的:0
比5
小的:0
比0
小的,没有
所以,该数组的逆序对共有5个
3.代码实现
public class Example3 {public static void main(String[] args) {int[] arr = {3, 2, 4, 5, 0};System.out.println(process(arr, 0, arr.length - 1));}private static int process(int[] arr, int l, int r) {if (l == r) {return 0;}int mid = l + ((r - l) >> 1);int leftR = process(arr, l, mid);int rightR = process(arr, mid + 1, r);return leftR + rightR + merge(arr, l, mid, r);}private static int merge(int[] arr, int l, int mid, int r) {int[] temp = new int[r - l + 1];int i = 0;int p1 = l;int p2 = mid + 1;int sum = 0;while (p1 <= mid && p2 <= r){sum += arr[p1] > arr[p2] ? (mid - p1 + 1) : 0;temp[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];}while (p1 <= mid){temp[i++] = arr[p1++];}while (p2 <= r){temp[i++] = arr[p2++];}for (int j = 0; j < temp.length; j++) {arr[l + j] = temp[j];}return sum;}
}
🌴总结
文章中代码的编写使用的都是Java基础知识,多加练习熟能生巧。
本文中若是有出现的错误请在评论区或者私信指出,我再进行改正优化,如果文章对你有所帮助,请给博主一个宝贵的三连,感谢大家😘!!!
相关文章:
Java的归并排序
不爱生姜不吃醋⭐️⭐️⭐️ 如果本文有什么错误的话欢迎在评论区中指正 与其明天开始,不如现在行动! 文章目录 🌴前言🌴一.归并排序1.概念2.时间复杂度3.代码实现 🌴二、小和问题1.概念2.举例3.代码实现 🌴…...
B. The Walkway Codeforces Round 893 (Div. 2)
Problem - B - Codeforces 题目大意:小明在数轴上要从1走到n,其中某些坐标上有一些饼干店,共m个,小明身上也有无限多的饼干,它首先一定会在1的位置吃一个饼干,在每个饼干店的位置会吃一个,在前…...
第四篇 DirectShow 采集调用结构关系
第一篇: DirectShow视频采集_会头痛的可达鸭的博客-CSDN博客 一、GraphBuilder 1、IFilterGraph2、IGraphBuilder、ICaptureGraphBuiler2 (1)、CLSID IFilterGraph CLSID_FilterGraphIFilterGraph2 CLSID_CaptureGraphBuilderIGraphBuilder CL…...

2605. 从两个数字数组里生成最小数字
文章目录 Tag题目来源题目解读解题思路方法一:枚举比较法方法二:集合的位运算表示法 写在最后 Tag 【贪心】【位运算】【数组】 题目来源 2605. 从两个数字数组里生成最小数字 题目解读 给定两个各自只包含数字 1 到 9 的两个数组,每个数组…...

服务器发送事件Server-sent events详解与示例
Server-sent events 服务端进行数据推送除了WebSocket之外,还可以使用Server-Send-Event方案。 与 WebSocket不同的是,服务器发送事件是单向的。数据消息只能从服务端到发送到客户端(如用户的浏览器)。这使其成为不需要从客户端…...

SOLIDWORKS 多实体的建模方式
SOLIDWORKS多实体是SOLIDWORKS中一个非常有用的功能。在SOLIDWORKS中,对于模型的设定通常被大家所熟知的有以下几种类型:零件、装配体以及工程图。 其实还有一种划分,就是多实体。严格意义上来说,多实体既不属于零件也不属于装配体…...

NSSCTF web 刷题记录1
文章目录 前言题目[GXYCTF 2019]禁止套娃方法一方法二 [NCTF 2019]Fake XML cookbook[NSSRound#7 Team]ec_RCE[NCTF 2018]Flask PLUS 前言 今天是2023.9.3,大二开学前的最后一天。老实说ctf的功力还是不太够做的题目太少,新学期新气象。不可急于求成&am…...

遥感指数数据库
目前遥感指数多种多样,那怎么针对不同的应用领域选择合适的植被指数?不同卫星又有哪些可以反演的指数? Henrich等人开发了Index Database(网址:https://www.indexdatabase.de/),总结了目前主流的遥感指数,…...

如何让insert程序速度快,可以试试联合SQL(insert 和 select 一起使用)?
查询添加可选择SQL执行,速度远超程序执行 insert 和 select案例 insert into 表1(列1,列2,列3,...) select 列1,列2,列3,...from表2(GROUP BY 列)116511 条数据 耗时45秒, 如果是程序查询然后再insert,则需要30分钟左右!&#x…...

IP地址、网关、网络/主机号、子网掩码关系
一、IP地址 IP地址组成 IP地址分为两个部分:网络号和主机号 (1)网络号:标识网段,保证相互连接的两个网段具有不同的标识。 (2)主机号:标识主机,同一网段内,主机之间具有相同的网…...
使用skvideo.io.vread读取avi视频,报错“No way to determine width or height from video...”
问题描述: 一开始安装sk-video,在使用skvideo.io.vread读取avi视频,报错“No way to determine width or height from video. Need -s in inputdict. Consult documentation on I/O.” 解决方案: 1. 卸载sk-video pip uninsta…...

Nomad 系列-安装
系列文章 Nomad 系列文章 Nomad 简介 开新坑!近期算是把自己的家庭实验室环境初步搞好了,终于可以开始进入正题研究了。 首先开始的是 HashiCorp Nomad 系列,欢迎阅读。 关于 Nomad 的简介,之前在 大规模 IoT 边缘容器集群管…...

网络版五子棋C++实现
目录 1.项目介绍 2.开发环境 3.核心技术 4.环境搭建 5.WebSocketpp介绍 5.1WebSocketpp是什么 5.2为什么使用WebSocketpp 5.3原理解析: 5.4WebSocketpp主要特性 6.WebSocketpp使用 7.JsonCpp使用 8.MySQL API 9.项目模块设计以及流程图 10.封装日志宏…...

项目招标投标公众号小程序开源版开发
项目招标投标公众号小程序开源版开发 以下是一个招标投标公众号小程序的功能列表: 用户注册与登录:用户可以注册账号并登录公众号小程序。项目发布:用户可以发布招标项目的详细信息,包括项目名称、招标单位、项目描述、招标要求…...

华为OD机试-机器人走迷宫
题目描述 机器人走一个迷宫,给出迷宫的x和y(x*y的迷宫)并且迷宫中有障碍物,输入k表示障碍物有k个,并且会将障碍物的坐标挨个输入. 机器人从0,0的位置走到x,y的位置并且只能向x,y增加的方向走,不能回退. 如代码类注释展示的样子,#表示可以走的方格,0代表障碍,机器人从0,0的位置…...
Jenkins搭建步骤Linux环境
1、进入目标目录开始准备环境 安装jdk 安装maven 安装tomcat 安装node 下载Jenkins.war并且拷贝进tomcat的webapp的文件夹下。 环境变量配置如下自行更改: #--------------For JDK---------------- export JAVA_HOME/usr/local/java/jdk1.8.0_192 export PATH/usr…...

2023 AZ900备考
文章目录 如何学习最近准备考AZ900考试,找了一圈文档,结果发现看那么多文档,不如直接看官方的教程https://learn.microsoft.com/zh-cn/certifications/exams/az-900/ ,简单直接,突然想到纳瓦尔宝典中提到多花时间进行思…...

青翼科技基于VITA57.1的16路数据收发处理平台产品手册
FMC211是一款基于VITA57.1标准规范的实现16路LVDS数据采集、1路光纤数据收发处理FMC子卡模块。 该板卡支持2路CVBS(复合视频)视频输入,能够自动检测标准的模拟基带电视信号,并将其转变为8位ITU-R.656接口信号或者4:2:2分量视频信…...
Ansible_自动化运维实战(一)
1.DELL的一款服务器的价格、型号、配置(CPU,内存、硬盘、支持的RAID功能) DELL 服务器的定价、型号和配置因型号而异,可以通过访问 DELL 官方网站或联系 DELL 客户服务获取具体信息。一种示例是 DELL PowerEdge R740,其…...

说说Flink中的State
分析&回答 基本类型划分 在Flink中,按照基本类型,对State做了以下两类的划分: Keyed State,和Key有关的状态类型,它只能被基于KeyedStream之上的操作,方法所使用。我们可以从逻辑上理解这种状态是一…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...

对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...

页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...