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

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小的数:13
2左边比2小的数:1
5左边比5小的数:1342
所以,小和为: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小的:20
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的归并排序

不爱生姜不吃醋⭐️⭐️⭐️ 如果本文有什么错误的话欢迎在评论区中指正 与其明天开始&#xff0c;不如现在行动&#xff01; 文章目录 &#x1f334;前言&#x1f334;一.归并排序1.概念2.时间复杂度3.代码实现 &#x1f334;二、小和问题1.概念2.举例3.代码实现 &#x1f334…...

B. The Walkway Codeforces Round 893 (Div. 2)

Problem - B - Codeforces 题目大意&#xff1a;小明在数轴上要从1走到n&#xff0c;其中某些坐标上有一些饼干店&#xff0c;共m个&#xff0c;小明身上也有无限多的饼干&#xff0c;它首先一定会在1的位置吃一个饼干&#xff0c;在每个饼干店的位置会吃一个&#xff0c;在前…...

第四篇 DirectShow 采集调用结构关系

第一篇: DirectShow视频采集_会头痛的可达鸭的博客-CSDN博客 一、GraphBuilder 1、IFilterGraph2、IGraphBuilder、ICaptureGraphBuiler2 (1)、CLSID IFilterGraph CLSID_FilterGraphIFilterGraph2 CLSID_CaptureGraphBuilderIGraphBuilder CL…...

2605. 从两个数字数组里生成最小数字

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

服务器发送事件Server-sent events详解与示例

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

SOLIDWORKS 多实体的建模方式

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

NSSCTF web 刷题记录1

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

遥感指数数据库

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

如何让insert程序速度快,可以试试联合SQL(insert 和 select 一起使用)?

查询添加可选择SQL执行&#xff0c;速度远超程序执行 insert 和 select案例 insert into 表1(列1,列2,列3,...) select 列1,列2,列3,...from表2(GROUP BY 列)116511 条数据 耗时45秒&#xff0c; 如果是程序查询然后再insert&#xff0c;则需要30分钟左右&#xff01;&#x…...

IP地址、网关、网络/主机号、子网掩码关系

一、IP地址 IP地址组成 IP地址分为两个部分&#xff1a;网络号和主机号 &#xff08;1&#xff09;网络号:标识网段&#xff0c;保证相互连接的两个网段具有不同的标识。 &#xff08;2&#xff09;主机号:标识主机&#xff0c;同一网段内&#xff0c;主机之间具有相同的网…...

使用skvideo.io.vread读取avi视频,报错“No way to determine width or height from video...”

问题描述&#xff1a; 一开始安装sk-video&#xff0c;在使用skvideo.io.vread读取avi视频&#xff0c;报错“No way to determine width or height from video. Need -s in inputdict. Consult documentation on I/O.” 解决方案&#xff1a; 1. 卸载sk-video pip uninsta…...

Nomad 系列-安装

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

网络版五子棋C++实现

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

项目招标投标公众号小程序开源版开发

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

华为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的文件夹下。 环境变量配置如下自行更改&#xff1a; #--------------For JDK---------------- export JAVA_HOME/usr/local/java/jdk1.8.0_192 export PATH/usr…...

2023 AZ900备考

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

青翼科技基于VITA57.1的16路数据收发处理平台产品手册

FMC211是一款基于VITA57.1标准规范的实现16路LVDS数据采集、1路光纤数据收发处理FMC子卡模块。 该板卡支持2路CVBS&#xff08;复合视频&#xff09;视频输入&#xff0c;能够自动检测标准的模拟基带电视信号&#xff0c;并将其转变为8位ITU-R.656接口信号或者4:2:2分量视频信…...

Ansible_自动化运维实战(一)

1.DELL的一款服务器的价格、型号、配置&#xff08;CPU&#xff0c;内存、硬盘、支持的RAID功能&#xff09; DELL 服务器的定价、型号和配置因型号而异&#xff0c;可以通过访问 DELL 官方网站或联系 DELL 客户服务获取具体信息。一种示例是 DELL PowerEdge R740&#xff0c;其…...

说说Flink中的State

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

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

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 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

对WWDC 2025 Keynote 内容的预测

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

页面渲染流程与性能优化

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

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;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年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...