Java 归并排序
归并排序(Merge Sort)是一种基于分治法的排序算法。它将一个大数组分成两个较小的子数组,分别对每个子数组进行排序,然后再将这两个已排序的子数组合并成一个完整的已排序数组。归并排序的时间复杂度为 O(n log n),其中 n 是数组的大小。
以下是一个 Java 实现归并排序的示例:
public class MergeSort { // 主函数,用于测试归并排序 public static void main(String[] args) { int[] array = {38, 27, 43, 3, 9, 82, 10}; System.out.println("给定数组:"); printArray(array); mergeSort(array, 0, array.length - 1); System.out.println("\n排序后的数组:"); printArray(array); } // 归并排序函数 public static void mergeSort(int[] array, int left, int right) { if (left < right) { // 找到中间点 int middle = (left + right) / 2; // 对左半部分进行排序 mergeSort(array, left, middle); // 对右半部分进行排序 mergeSort(array, middle + 1, right); // 合并已排序的左右两部分 merge(array, left, middle, right); } } // 合并函数 public static void merge(int[] array, int left, int middle, int right) { // 找到两个子数组的大小 int n1 = middle - left + 1; int n2 = right - middle; // 创建临时数组 int[] leftArray = new int[n1]; int[] rightArray = new int[n2]; // 拷贝数据到临时数组 for (int i = 0; i < n1; ++i) leftArray[i] = array[left + i]; for (int j = 0; j < n2; ++j) rightArray[j] = array[middle + 1 + j]; // 合并临时数组到原数组 // 初始索引分别为两个子数组的起始位置 int i = 0, j = 0; // 初始索引为合并子数组的起始位置 int k = left; while (i < n1 && j < n2) { if (leftArray[i] <= rightArray[j]) { array[k] = leftArray[i]; i++; } else { array[k] = rightArray[j]; j++; } k++; } // 拷贝左子数组剩余的元素(如果有) while (i < n1) { array[k] = leftArray[i]; i++; k++; } // 拷贝右子数组剩余的元素(如果有) while (j < n2) { array[k] = rightArray[j]; j++; k++; } } // 打印数组函数 public static void printArray(int[] array) { int n = array.length; for (int i = 0; i < n; ++i) System.out.print(array[i] + " "); System.out.println(); }
}
代码解释:
mergeSort方法:- 递归地将数组分成左右两部分,直到每部分只有一个元素或为空。
- 递归调用
mergeSort方法对左右两部分进行排序。 - 调用
merge方法将已排序的左右两部分合并成一个完整的已排序数组。
merge方法:- 创建两个临时数组
leftArray和rightArray分别存储左右两部分。 - 将左右两部分分别拷贝到临时数组中。
- 使用两个指针
i和j分别遍历临时数组leftArray和rightArray。 - 使用一个指针
k遍历原数组,根据临时数组中的元素大小,将较小的元素依次拷贝回原数组。 - 如果某一临时数组的元素已经拷贝完,则将另一临时数组的剩余元素拷贝回原数组。
- 创建两个临时数组
printArray方法:- 用于打印数组中的元素。
运行结果:
程序运行后,会先打印给定的数组,然后打印排序后的数组。
归并排序是一个稳定的排序算法,适用于大多数需要排序的场景。它的空间复杂度为 O(n),因为需要额外的临时数组来存储子数组的元素。
相关文章:
Java 归并排序
归并排序(Merge Sort)是一种基于分治法的排序算法。它将一个大数组分成两个较小的子数组,分别对每个子数组进行排序,然后再将这两个已排序的子数组合并成一个完整的已排序数组。归并排序的时间复杂度为 O(n log n),其中…...
20241008深度学习动手篇
文章目录 1.如何写一个神经网络进行训练?1.1创建一个子类,搭建你需要的神经网络结构1.2 加载数据集1.3 自定义一些指标评估函数1.4训练1.5 结果展示 2.参考文献 1.如何写一个神经网络进行训练? 1.1创建一个子类,搭建你需要的神经网络结构 # File: 241008LeNet.py # Author:…...
对序列化反序列化在项目中的使用优化
文章目录 序列化是什么?常见的序列化协议使用序列化反序列化序列化List反序列化List 查看源码,分析不足进行改善 序列化是什么? 如果我们需要持久化 Java 对象比如将 Java 对象保存在文件中,或者在网络传输 Java 对象,…...
查看 git log的过程中看到 :说明日志输出可能超出屏幕大小,系统进入了分页模式
在命令行提示符中,通常 : 表示系统等待进一步的输入。如果你在查看 git log 的过程中看到 :,说明日志输出可能超出屏幕大小,系统进入了分页模式,默认使用 less 命令查看内容。 此时你可以: 按 q 退出日志查看。按 En…...
Linux--信号量详解
目录 一、信号量 1、信号量相关函数 2、多线程环形队列生产消费模型 3、实现代码 信号量是将整体的资源分割成多份使用 信号量本质是对资源的预定机制 一、信号量 1、信号量相关函数 创建信号量: sem_init: int sem_init(sem_t *sem, int pshared, unsigned int value); …...
【重学 MySQL】五十一、更新和删除数据
【重学 MySQL】五十一、更新和删除数据 更新数据删除数据注意事项 在MySQL中,更新和删除数据是数据库管理的基本操作。 更新数据 为了更新(修改)表中的数据,可使用UPDATE语句。UPDATE语句的基本语法如下: UPDATE ta…...
Web3与人工智能的交叉应用探索
随着数字技术的发展,Web3与人工智能(AI)之间的结合正逐渐成为一个重要的研究领域。Web3技术旨在实现更加去中心化和透明的互联网,而人工智能则在数据分析、自动化决策和增强人类能力方面展示了巨大的潜力。 1. 去中心化数据管理与…...
【springboot9736】基于springboot+vue的逍遥大药房管理系统
作者主页:Java码库 主营内容:SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app等设计与开发。 收藏点赞不迷路 关注作者有好处 文末获取源码 项目描述 伴随着全球信息化发展,行行业业都与计算机技…...
四.网络层(上)
目录 4.1网络层功能概述 4.2 SDN基本概念 4.3 路由算法与路由协议 4.3.1什么是路由协议? 4.3.2什么是路由算法? 4.3.3路由算法分类 (1)静态路由算法 (2)动态路由算法 ①全局性 OSPF协议与链路状态算法 ②分散性 RIP协议与距离向量算法 4.3.…...
Leecode热题100-56.合并区间
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。 示例 1: 输入:intervals [[1,3…...
安全帽未佩戴预警系统 劳保防护用品穿戴监测系统 YOLO
在建筑、矿山、电力等高危行业中,工人面临着各种潜在的危险,如高空坠物、物体打击等。安全帽能够有效地分散和吸收冲击力,大大降低头部受伤的严重程度。一旦工人未正确佩戴安全帽,在遭遇危险时,头部将直接暴露在危险之…...
【python机器学习】线性回归 拟合 欠拟合与过拟合 以及波士顿房价预估案例
文章目录 线性回归之波士顿房价预测案例 欠拟合与过拟合线性回归API 介绍:波士顿房价预测数据属性:机器学习代码实现 拟合 过拟合 欠拟合 模拟 及处理方法(正则化处理)导包定义函数表示欠拟合定义函数表示拟合定义函数表示过拟合 正则化处理过拟合L1正则化L2正则化 线性回归之波…...
IT招聘乱象的全面分析
近年来,IT行业的招聘要求似乎越来越苛刻,甚至有些不切实际。许多企业在招聘时,不仅要求前端工程师具备UI设计能力,还希望后端工程师精通K8S服务器运维,更有甚至希望研发经理掌握所有前后端框架和最新开发技术。这种招聘…...
一入递归深似海,算法之美无止境
最近在刷leetcode hot100,在写二叉树中最大路径和的时候,看到了一个佬对递归的理解,深受启发,感觉自己对于递归的题又行了!!! 这里给大家分享一下(建立大家先去尝试一下这道题再来看 124. 二叉树中的最大路径和 二叉树中的 路径 被定义为一条节点序列,序列中每…...
进程的状态的理解(概念+Linux)
文章目录 进程的状态并行和并发物理和逻辑 时间片进程具有独立性等待的本质运行阻塞标记挂起等待 Linux下的进程状态(一)运行状态(R - running)(二)睡眠状态(S - sleeping)ÿ…...
Apache Linkis + OceanBase:如何提升数据分析效率
计算中间件 Apache Linkis 构建了一个计算中间件层,以实现上层应用程序和底层数据引擎之间的连接、治理和编排。目前,已经支持通过数据源的功能,实现用户通过Linkis 对接并使用 OceanBase数据库。 本文详细阐述了在 Apache Linkis v1.3.2中&a…...
Day01-postgresql数据库基础入门培训
Day01-postgresql数据库基础入门培训 1、PostgresQL数据库简介2、PostgreSQL行业生态应用3、PostgreSQL版本发展与特性4、PostgreSQL体系结构介绍5、PostgreSQL与MySQL的区别6、PostgreSQL与Oracle、MySQL的对比 1、PostgresQL数据库简介 PostgreSQL【简称:PG】是加…...
打卡第四天 P1081 [NOIP2012 提高组] 开车旅行
今天是我打卡第四天,做个省选/NOI−题吧(#^.^#) 原题链接:[NOIP2012 提高组] 开车旅行 - 洛谷 题目描述 输入格式 输出格式 输入输出样例 输入 #1 4 2 3 1 4 3 4 1 3 2 3 3 3 4 3 输出 #1 1 1 1 2 0 0 0 0 0 输入 #2 10 4 5 6 1 …...
Jenkins Pipline流水线
提到 CI 工具,首先想到的就是“CI 界”的大佬--]enkjns,虽然在云原生爆发的年代,蹦出来了很多云原生的 CI 工具,但是都不足以撼动 Jenkins 的地位。在企业中对于持续集成、持续部署的需求非常多,并且也会经常有-些比较复杂的需求,此时新生的 CI 工具不足以支撑这些很…...
鸿蒙harmonyos next flutter混合开发之开发FFI plugin
创建FFI plugin summation,默认创建的FFI plugin是求两个数的和 flutter create --templateplugin_ffi summation --platformsandroid,ios,ohos 创建my_application flutter create --org com.example my_application 在my_application项目中文件pubspec.yaml引…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
【Ftrace 专栏】Ftrace 参考博文
ftrace、perf、bcc、bpftrace、ply、simple_perf的使用Ftrace 基本用法Linux 利用 ftrace 分析内核调用如何利用ftrace精确跟踪特定进程调度信息使用 ftrace 进行追踪延迟Linux-培训笔记-ftracehttps://www.kernel.org/doc/html/v4.18/trace/events.htmlhttps://blog.csdn.net/…...
python读取SQLite表个并生成pdf文件
代码用于创建含50列的SQLite数据库并插入500行随机浮点数据,随后读取数据,通过ReportLab生成横向PDF表格,包含格式化(两位小数)及表头、网格线等美观样式。 # 导入所需库 import sqlite3 # 用于操作…...
智警杯备赛--excel模块
数据透视与图表制作 创建步骤 创建 1.在Excel的插入或者数据标签页下找到数据透视表的按钮 2.将数据放进“请选择单元格区域“中,点击确定 这是最终结果,但是由于环境启不了,这里用的是自己的excel,真实的环境中的excel根据实训…...
