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

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...