当前位置: 首页 > 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…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...