当前位置: 首页 > 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;方法所使用。我们可以从逻辑上理解这种状态是一…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...