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

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...