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

Java排序算法之归并排序

 图解

归并排序是一种效率比较高的分治排序算法,主要分为两个步骤,分别为“分”和“并”。

  1. 分:将序列不断二分,直到每个子序列只有一个元素为止。

  2. 并:将相邻两个子序列进行合并,合并时比较两个子序列的元素大小,按照从小到大的顺序放入新的序列中。

是一种分治算法,在每轮排序中将待排序数组分成两部分,递归地将每个子数组排序,最后将两个排好序的子数组合并成一个有序数组。

具体实现如下:

  1. 将待排序数组分成两个子数组,每个子数组包含原数组的一半元素,如果原数组长度为奇数,则一个子数组比另一个多一个元素。

  2. 递归地对每个子数组进行归并排序,直到子数组长度为1。

  3. 合并两个排好序的子数组。将两个子数组中的最小元素依次比较,将较小的元素放入新数组中,直到其中一个子数组的元素全部被放入新数组中,此时将另一个子数组中的剩余元素直接放到新数组的尾部。

  4. 返回合并后的有序数组。

归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。它是一种稳定的排序算法,适用于各种数据类型的排序。

以下是Java实现归并排序的代码:

public class MergeSort {public static void mergeSort(int[] arr, int left, int right) {if (left >= right) {return;}int mid = (left + right) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}private static void merge(int[] arr, int left, int mid, int right) {// 创建一个临时数组存放排序后的元素int[] temp = new int[right - left + 1];int i = left;int j = mid + 1;int k = 0;while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}while (i <= mid) {temp[k++] = arr[i++];}while (j <= right) {temp[k++] = arr[j++];}// 将排序后的元素拷贝回原数组for (int p = 0; p < temp.length; p++) {arr[left + p] = temp[p];}}public static void main(String[] args) {int[] arr = {5, 3, 8, 4, 2, 1, 10, 7};mergeSort(arr, 0, arr.length - 1);for (int i : arr) {System.out.print(i + " ");}}
}

输出结果为:1 2 3 4 5 7 8 10

相关文章:

Java排序算法之归并排序

图解 归并排序是一种效率比较高的分治排序算法&#xff0c;主要分为两个步骤&#xff0c;分别为“分”和“并”。 分&#xff1a;将序列不断二分&#xff0c;直到每个子序列只有一个元素为止。 并&#xff1a;将相邻两个子序列进行合并&#xff0c;合并时比较两个子序列的元素…...

【Phoenix】请求的生命周期

本文的目的是讨论Phoenix请求的生命周期。我们实战添加两个新的页面&#xff0c;并讨论整个过程是如何串起来的。 让我们从添加第一个新页面开始。 添加一个新页面 web应用通常通过将HTTP方法和路径映射到应用的某个函数来处理请求。Phoenix通过路由器来实现这个匹配。例如将…...

Ps:利用 AI 技术创建人像皮肤图层蒙版

Photoshop 并没有提供专门选择人像皮肤的工具或命令&#xff08;色彩范围中的肤色选择非常不精准&#xff09;&#xff0c;但较新版的 Camera Raw 滤镜则提供了基于 AI 技术的选择人物并创建面部和身体皮肤蒙版的功能。 如果能将 Camera Raw 滤镜中创建的 AI 皮肤蒙版转换成 Ps…...

内存泄漏、new、delete

1. 内存泄漏 内存泄漏&#xff1a;指针被销毁&#xff0c;指针指向的空间依旧存在 2. new过程 与内存分配、构造函数有关 1&#xff09;分配空间&#xff1a;void* mem operator new( sizeof( ) )&#xff0c;内部调用malloc 2&#xff09;static_cast<目标类型>(mem) …...

php在线审稿系统mysql数据库web结构layUI布局apache计算机软件工程网页wamp

一、源码特点 php在线审稿系统是一套完善的web设计系统mysql数据库 &#xff0c;对理解php编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。 php在线审稿系统 代码 https://download.csdn.net/download/qq_41221322/885…...

【华为HCIP | 华为数通工程师】ISIS 高频题(1)

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…...

Netty+SpringBoot 打造一个 TCP 长连接通讯方案

项目背景 最近公司某物联网项目需要使用socket长连接进行消息通讯&#xff0c;捣鼓了一版代码上线&#xff0c;结果BUG不断&#xff0c;本猿寝食难安&#xff0c;于是求助度娘&#xff0c;数日未眠项目终于平稳运行了&#xff0c;本着开源共享的精神&#xff0c;本猿把项目代码…...

2023.11.15 每日一题(AI自生成应用)【C++】【Python】【Java】【Go】 动态路径分析

目录 一、题目 二、解决方法 三、改进 一、题目 背景&#xff1a; 在一个城市中&#xff0c;有数个交通节点&#xff0c;每个节点间有双向道路相连。每条道路具有一个初始权重&#xff0c;代表通行该路段的成本&#xff08;例如时间、费用等&#xff09;。随着时间的变化&am…...

【libGDX】初识libGDX

1 前言 libGDX 是一个开源且跨平台的 Java 游戏开发框架&#xff0c;于 2010 年 3 月 11 日推出 0.1 版本&#xff0c;它通过 OpenGL ES 2.0/3.0 渲染图像&#xff0c;支持 Windows、Linux、macOS、Android、iOS、Web 等平台&#xff0c;提供了统一的 API&#xff0c;用户只需要…...

VIVADO+FPGA调试记录

vivadoFPGA调试记录 vitis编译vivado导出的硬件平台&#xff0c;提示xxxx.h file cant find vitis编译vivado导出的硬件平台&#xff0c;提示’xxxx.h file cant find’ 此硬件平台中&#xff0c;包含有AXI接口类型的ip。在vitis编译硬件平台时&#xff0c;经常会报错&#xf…...

Android——Gradle插件gradle-wrapper.properties

一、Android Studio版本&#xff0c;Android Gradle插件版本&#xff0c;Gradle版本 Android Studio 通过Android Gradle插件 使用 Gradle来构建代码&#xff1b; Android Studio每次升级后&#xff0c; Android Gradle 插件自动更新&#xff0c;对应的Gradle版本也会变动&…...

iOS应用加固方案解析:ipa加固安全技术全面评测

在移动应用开发领域&#xff0c;iOS应用的安全性一直备受关注。ipaguard作为一款专业的iOS应用加固方案&#xff0c;采用混淆加密技术&#xff0c;旨在保护应用免受破解、逆向和篡改等风险。本文将深入探讨ipaguard的产品功能、安全技术及其在iOS应用加固领域中的核心优势和特色…...

过滤器模式 rust和java的实现

文章目录 过滤器模式实现 过滤器模式实现javarustjavarust rust代码仓库 过滤器模式 过滤器模式&#xff08;Filter Pattern&#xff09;或标准模式&#xff08;Criteria Pattern&#xff09;是一种设计模式&#xff0c;这种模式允许开发人员使用不同的标准来过滤一组对象&…...

Feature Pyramid Networks for Object Detection(2017.4)

文章目录 Abstract1. Introduction3. Feature Pyramid NetworksBottom-up pathwayTop-down pathway and lateral connections 7. Conclusion FPN Abstract 特征金字塔是识别系统中检测不同尺度物体的基本组成部分。但最近的深度学习对象检测器避免了金字塔表示&#xff0c;部分…...

Python3基础模块 random

Python3基础模块 random import random #作用&#xff1a;生成随机数使用dir(module)查看模块内容 >>> import random >>> dir(random) [BPF, LOG4, NV_MAGICCONST, RECIP_BPF, Random, SG_MAGICCONST, SystemRandom, TWOPI, _BuiltinMethodType, _MethodT…...

ubuntu安装pgsql16

ubuntu安装postgresSQL 官网地址&#xff1a; https://www.postgresql.org/download/ 1.安装 # 添加源 sudo sh -c echo "deb https://apt.postgresql.org/pub/repos/apt $(lsb_release -cs)-pgdg main" > /etc/apt/sources.list.d/pgdg.list # 安装数字签名 w…...

数据管理70个名词解析

数据标准化70个名词解析 1、数据 是指任何以电子或者其他方式对信息的记录。在计算机科学技术中&#xff0c;“数据”是客观事物的符号表示&#xff0c;指所有可被输入到计算机中并可被计算机程序处理的符号的总称;在管理科学技术中&#xff0c;“数据”是描述事件或事物的属性…...

线性代数本质系列(二)矩阵乘法与复合线性变换,行列式,三维空间线性变换

本系列文章将从下面不同角度解析线性代数的本质&#xff0c;本文是本系列第二篇 向量究竟是什么&#xff1f; 向量的线性组合&#xff0c;基与线性相关 矩阵与线性相关 矩阵乘法与复合线性变换 三维空间中的线性变换 行列式 逆矩阵&#xff0c;列空间&#xff0c;秩与零空间 克…...

Linux-CentOS重要模块

软件包管理器&#xff1a;CentOS使用Yum&#xff08;Yellowdog Updater, Modified&#xff09;作为其包管理器。Yum提供了一种方便的方式来安装、更新和删除软件包&#xff0c;并自动解决依赖关系。 RPM&#xff1a;RPM&#xff08;RPM Package Manager&#xff09;是CentOS中…...

posix定时器的使用

POSIX定时器是基于POSIX标准定义的一组函数&#xff0c;用于实现在Linux系统中创建和管理定时器。POSIX定时器提供了一种相对较高的精度&#xff0c;可用于实现毫秒级别的定时功能。 POSIX定时器的主要函数包括&#xff1a; timer_create()&#xff1a;用于创建一个定时器对象…...

群晖更换RAID类型无需重建服务,保持Volume磁盘盘符不变

我的环境&#xff1a;DSM型号&#xff1a;DS3617xs&#xff08;黑群晖&#xff09;系统版本&#xff1a;DSM 7.1.1-42962 Update 6硬盘数据库更新时间&#xff1a;2026-01-23更改前磁盘序号&#xff08;btrfs&#xff09;&#xff1a;Raid1&#xff08;volume1&#xff09;&…...

AI正冲击金融岗!高薪职业如何守住饭碗?金融人转行AI指南

AI技术正全面冲击金融行业&#xff0c;初级分析师、风控专员、客服等中低端认知劳动密集型岗位面临被替代风险。但高端投行、深度研究、资源型和创新型岗位短期内仍安全。金融人转型AI有独特优势&#xff0c;如数据敏感性、业务理解力等。转型路径包括AI应用专家、金融科技产品…...

iOS设备支持文件管理指南:让Xcode兼容新旧iOS系统的实用方案

iOS设备支持文件管理指南&#xff1a;让Xcode兼容新旧iOS系统的实用方案 【免费下载链接】iOSDeviceSupport All versions of iOS Device Support 项目地址: https://gitcode.com/gh_mirrors/ios/iOSDeviceSupport 开发困境突破&#xff1a;iOS版本与Xcode的兼容性挑战 …...

Phi-4-mini-reasoning效果展示:含单位换算、科学计数法的复合型数学题求解

Phi-4-mini-reasoning效果展示&#xff1a;含单位换算、科学计数法的复合型数学题求解 1. 模型能力概览 Phi-4-mini-reasoning是一款专注于推理任务的文本生成模型&#xff0c;特别擅长处理需要多步逻辑推导的问题。与通用聊天模型不同&#xff0c;它更专注于"问题输入→…...

危废尾气治理厂家怎么选?CO超低排放技术与全场景危废焚烧烟气治理解决方案

随着我国危废处置行业监管体系持续完善&#xff0c;《危险废物焚烧污染控制标准》&#xff08;GB 18484-2020&#xff09;对危废焚烧烟气中一氧化碳&#xff08;CO&#xff09;等污染物设置了明确排放限值&#xff0c;北京、海南等多地更是出台严于国标的地方标准&#xff0c;其…...

LSTM预测不准?试试这个全局注意力“外挂”:一个PyTorch模块提升你的时序模型性能

LSTM预测不准&#xff1f;试试这个全局注意力“外挂”&#xff1a;一个PyTorch模块提升你的时序模型性能 当你发现精心调参的LSTM模型在预测股票价格、设备故障率或能源消耗时&#xff0c;总是错过关键转折点&#xff0c;问题可能不在你的数据清洗或超参选择——而是模型缺乏对…...

ThinkPHP6(TP6)控制器404问题排查与Nginx伪静态配置指南

1. 为什么你的TP6控制器总是404&#xff1f; 最近帮朋友排查一个ThinkPHP6项目&#xff0c;明明控制器写得没问题&#xff0c;路由也配置了&#xff0c;但一访问就蹦出个404页面。这种问题在新手部署TP6时特别常见&#xff0c;尤其是用Nginx服务器的环境。我自己第一次用TP6时也…...

3种方法永久解决IDM激活弹窗问题 开源工具全解析

3种方法永久解决IDM激活弹窗问题 开源工具全解析 【免费下载链接】IDM-Activation-Script IDM Activation & Trail Reset Script 项目地址: https://gitcode.com/gh_mirrors/id/IDM-Activation-Script Internet Download Manager&#xff08;IDM&#xff09;作为一款…...

高效代码分析利器:cloc工具全场景使用指南

1. 为什么你需要cloc这个代码统计神器 第一次接手一个遗留项目时&#xff0c;我盯着密密麻麻的目录树发愁&#xff1a;这堆代码到底有多少实际内容&#xff1f;注释占比多少&#xff1f;不同语言的文件各有多少&#xff1f;直到同事推荐了cloc工具&#xff0c;输入一行命令就得…...

实战指南:借鉴vmware官网混合云方案,用快马平台生成高可用应用部署模板

今天在VMware官网上研究混合云方案时&#xff0c;发现他们的企业级架构设计特别值得借鉴。正好最近在用InsCode(快马)平台做项目部署&#xff0c;就尝试把官网的混合云方案转化成可落地的模板。整个过程比想象中顺利&#xff0c;分享下我的实战经验。 架构设计思路 VMware官网…...