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

深入了解归并排序:原理、性能分析与 Java 实现

归并排序(Merge Sort)是一种高效且稳定的排序算法,其优雅的分治策略使它成为排序领域的一颗明珠。它的核心思想是将一个未排序的数组分割成两个子数组,然后递归地对子数组进行排序,最后将这些排好序的子数组合并起来。

mergesort.jpg

什么是归并排序?

归并排序是一种分治策略的排序算法,它的核心思想是将数组分成两个子数组,递归地对子数组进行排序,然后将排序好的子数组合并起来,最终得到有序的数组。归并排序的关键步骤包括:

  1. 分割阶段: 将数组分成两个子数组,通常是平均分割。

  2. 递归排序: 递归地对左右两个子数组进行排序。

  3. 合并阶段: 将排好序的子数组合并成一个新的有序数组。

mergesort.png

归并排序的性能分析

归并排序在性能方面有以下特点:

  • 时间复杂度: 归并排序的平均、最好和最坏情况下时间复杂度均为 O ( n l o g n ) O(n log n) O(nlogn),这使它成为高效的排序算法。

  • 空间复杂度: 归并排序通常需要额外的内存空间来存储临时数据,因此其空间复杂度为 O ( n ) O(n) O(n)

  • 稳定性: 归并排序是稳定的排序算法,相等元素的相对顺序在排序后不会改变。

  • 适用场景: 归并排序适用于各种数据规模和数据类型,特别适用于外部排序,如大文件的排序。

Java 代码实现

以下是使用 Java 实现归并排序的示例代码:

public class Test {public static void main(String[] args) {int[] arr = new int[]{7,5,2,3,6,4};System.out.println("原始数组:"+ Arrays.toString(arr));mergeSort(arr);System.out.println("排序后的数组:"+ Arrays.toString(arr));}// 归并排序的入口方法public static void mergeSort(int[] arr) {// 针对特殊情况,数组为空或只有一个元素时,无需排序if(arr == null || arr.length <= 1  ){return;}// 创建一个临时数组用于归并操作int[] temp = new int[arr.length];// 调用实际的排序方法,传入数组、左边界、右边界和临时数组sort(arr, 0, arr.length - 1, temp);}// 归并排序的核心排序方法(递归调用的方法)public static void sort(int[] arr,int left,int right,int[] temp) {//递归终止的条件if(left < right){//计算中间位置分割的下标int mid = (right + left) / 2;// 递归对左半部分进行排序sort(arr, left, mid, temp);// 递归对右半部分进行排序sort(arr, mid+1, right, temp);//合并merge(arr,left,mid,right,temp);}}// 归并排序的核心归并方法public static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left;int j = mid + 1;int k = left;// 比较左右两部分的元素,并将较小的元素放入临时数组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 l = left; l <= right; l++) {arr[l] = temp[l];}}}

输出结果:

原始数组:[7, 5, 2, 3, 6, 4]
排序后的数组:[2, 3, 4, 5, 6, 7]

这段代码演示了如何使用 Java 实现归并排序算法。它通过递归将数组分割为子数组,然后合并这些子数组,最终得到排序完成的数组。

总结

总之,归并排序是一种高效、稳定的排序算法,适用于各种规模和类型的数据。虽然它的空间复杂度较高,但在实际应用中,它的性能通常非常出色。这使得它成为排序算法家族中的重要一员。

相关文章:

深入了解归并排序:原理、性能分析与 Java 实现

归并排序&#xff08;Merge Sort&#xff09;是一种高效且稳定的排序算法&#xff0c;其优雅的分治策略使它成为排序领域的一颗明珠。它的核心思想是将一个未排序的数组分割成两个子数组&#xff0c;然后递归地对子数组进行排序&#xff0c;最后将这些排好序的子数组合并起来。…...

docker stop了一个docker exec容器,要怎么再启动呢

docker restart <容器ID>...

【总结】kubernates 插件工具总结

在此记录工作中用到的关于 kubernates 的插件小工具&#xff0c;以防以后忘记 1、能显示 kubernates 所处上下文的插件 kube-ps1 github 地址&#xff1a; https://github.com/jonmosco/kube-ps1 效果 2、能方便切换 kubernates 上下文的插件 kubecm github 地址&#xff1…...

RK3588平台产测之ArmSoM-W3 DDR带宽监控

1. 简介 专栏总目录 ArmSoM团队在产品量产之前都会对产品做几次专业化的功能测试以及性能压力测试&#xff0c;以此来保证产品的质量以及稳定性 优秀的产品都要进行多次全方位的功能测试以及性能压力测试才能够经得起市场的检验 2. 环境介绍 硬件环境&#xff1a; ArmSoM-W…...

基于SpringBoot的作业管理系统设计与实现

目录 前言 一、技术栈 二、系统功能介绍 学生管理 教师管理 班级管理 作业管理 作业提交管理 作业点评管理 教师作业发布 学生作业提交 学生作业点评 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 使用旧方法对作业管理信息进行系统化管理已经不再…...

TailwindCss Functions Directives

一般都写在一个 css 文件。 Directives tailwindlayerapplyconfig 【一般放在最后面&#xff0c;import 导入其他 css 文件后】 tailwind base; tailwind components; tailwind utilities;layer base {h1 {apply text-2xl;}h2 {apply text-xl;} }layer components {.btn-blu…...

MDK自动生成带校验带SVN版本号的升级文件

MDK自动生成带校验带SVN版本号的升级文件 获取SVN版本信息 确保SVN安装了命令行工具&#xff0c;默认安装时不会安装命令行工具 编写一个模板头文件 svn_version.temp.h, 版本号格式为 1_0_0_SVN版本号 #ifndef __SVN_VERSION_H #define __SVN_VERSION_H#define SVN_REVISIO…...

如何打造一个网络框架模块对接服务器

一、了解网络框架的基本原理 在开始打造网络框架模块之前&#xff0c;首先需要了解网络框架的基本原理。网络框架是一个软件模块&#xff0c;用于处理网络通信的各种细节&#xff0c;包括数据传输、协议解析、错误处理等。常见的网络框架有HTTP、TCP/IP、WebSocket等。 对啦&…...

装饰器模式和 AOP 面向切片编程(设计模式与开发实践 P15)

文章目录 示例AOP 很多时候我们不希望一个类变得非常庞大&#xff0c;生来就包含很多职责。装饰器模式可以动态地给某个对象添加职责&#xff0c;而不会影响从这个类中派生的其他对象 为什么不用继承解决这个问题呢&#xff1f;如果用继承有可能会创造出数量庞大的子类&#x…...

Git迁移新仓库并保存历史提交记录

Git迁移新仓库并保存历史提交记录 第一步&#xff0c;从远程仓库克隆到本地 git clone https://gitee.com/oldxxx/oldxxx.git第二步&#xff0c;删除需要迁移的本地项目所关联的远程仓库地址 git remote remove origin第三步&#xff0c;关联新仓库的地址 git remote add o…...

MySql逗号分割的字段数据分解为多行

在 MySQL 中&#xff0c;你可以使用函数 REPLACE 和 SUBSTRING_INDEX 来将一行逗号分隔的数据分解为多行。 例如&#xff0c;假设你有一个表&#xff0c;其中包含一列 items&#xff0c;该列包含逗号分隔的字符串&#xff0c;如下所示&#xff1a; -------------------------…...

共生与共享:线程与进程的关系

&#x1f30d;前言 在计算机科学和操作系统领域&#xff0c;线程&#xff08;Thread&#xff09;和进程&#xff08;Process&#xff09;是两个关键概念。它们之间存在密切的关系&#xff0c;但又有着明显的区别。本文将深入探讨线程和进程之间的关系&#xff0c;以及它们在并…...

uniapp app或微信小程序项目使用gite仓库中的图片

注意&#xff1a;以下不适用于浏览器 第一步&#xff1a;新建仓库并上传图片 第二步&#xff1a;设置开源 第三步&#xff1a;复制图片地址如&#xff1a; https://gitee.com/jiaomingyu/project-img/blob/master/xkmb/haibao/moban/BB_474x707_0_da.png 第四步&#xff1…...

KUKA机器人如何强制输出或取消数字IO信号?

KUKA机器人如何强制输出或取消数字IO信号? 具体的操作方法和步骤可参考以下内容: 如下图所示,点击菜单—显示—输入/输出端,如下图所示,选择想要查看的信号,这里以数字输出端为例进行说明, 如下图所示,此时可以看到输出端信号的编号、名称和当前值,可以通过下拉滚动条…...

利用正则表达式进行数据采集和处理

目录 一、正则表达式的概述 二、正则表达式在数据采集中的运用 1、匹配和提取数据 2、数据清洗 3、数据验证 三、Python中的re模块介绍 1、re.match()方法 2、re.search()方法 总结 正则表达式是一种强大的文本处理工具&#xff0c;它可以用于模式匹配、提取、替换等操…...

javaScript:拖拽效果

目录 前言 实现思路 获取事件对象和坐标点&#xff1a; 配合定位&#xff1a; 鼠标事件监听&#xff1a; 拖拽过程&#xff1a; 停止拖拽&#xff1a; 代码实现&#xff08;代码讲解&#xff09; 前言 JavaScript的拖拽效果是一种常见的交互技术&#xff0c;它允许用户…...

【Unity3D编辑器开发】Unity3D中制作一个可以随时查看键盘对应KeyCode值面板,方便开发

推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客 大家好&#xff0c;我是佛系工程师☆恬静的小魔龙☆&#xff0c;不定时更新Unity开发技巧&#xff0c;觉得有用记得一键三连哦。 一、前言 在开发中&#xff0c;会遇到要使用监控键盘输入的KeyCode值来执…...

VUE echarts 柱状图、折线图 双Y轴 显示

weekData: [“1周”,“2周”,“3周”,“4周”,“5周”,“6周”,“7周”,“8周”,“9周”,“10周”], //柱状图横轴 jdslData: [150, 220, 430, 360, 450, 680, 100, 450, 680, 200], // 折线图的数据 cyslData: [100, 200, 400, 300, 500, 500, 500, 450, 480, 400], // 柱状图…...

Django开发之基础篇

Django基础篇 一、Django学习之路由二、Django学习之视图三、Django学习之静态资源 一、Django学习之路由 在 Django 中&#xff0c;路由&#xff08;URL 映射&#xff09;是将请求与视图函数关联起来的关键部分。路由定义了如何将特定的 URL 请求映射到 Django 应用程序中的视…...

在 centos7 上安装Docker

1、检查linux内核 Docker 运行在 CentOS 7 上&#xff0c;要求系统为64位、系统内核版本为 3.10 以上。 Docker 运行在 CentOS-6.5 或更高的版本的 CentOS 上&#xff0c;要求系统为64位、系统内核版本为 2.6.32-431 或者更高版本。 uname -r 2、使用 root 权限登录 Centos…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

【免费数据】2005-2019年我国272个地级市的旅游竞争力多指标数据(33个指标)

旅游业是一个城市的重要产业构成。旅游竞争力是一个城市竞争力的重要构成部分。一个城市的旅游竞争力反映了其在旅游市场竞争中的比较优势。 今日我们分享的是2005-2019年我国272个地级市的旅游竞争力多指标数据&#xff01;该数据集源自2025年4月发表于《地理学报》的论文成果…...

TCP/IP 网络编程 | 服务端 客户端的封装

设计模式 文章目录 设计模式一、socket.h 接口&#xff08;interface&#xff09;二、socket.cpp 实现&#xff08;implementation&#xff09;三、server.cpp 使用封装&#xff08;main 函数&#xff09;四、client.cpp 使用封装&#xff08;main 函数&#xff09;五、退出方法…...