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

排序算法-归并排序

属性

        归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使 子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:

        归并排序总结

        1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。

        2. 时间复杂度:O(N*logN)

        3. 空间复杂度:O(N)

        4. 稳定性:稳定

代码及注释(递归实现)

    //mergeSort是归并排序提供使用的方法public static void mergeSort(int[]arr){//用mergeSortChild进行递归排序mergeSortChild(arr,0,arr.length-1);}private static void mergeSortChild(int[]arr,int left,int right){//出递归if(left>=right){return;}//先计算出要排序数据的中间位置int mid=(left+right)/2;//先分别归并排序左边和右边的数据,排序好以后再将左边和右边的数据合并mergeSortChild(arr,left,mid);mergeSortChild(arr,mid+1,right);merge(arr,left,right);}private static void merge(int[]arr,int left,int right){int mid=(left+right)/2;//left和right范围的数据分为了两个部分//用s1,e1表示第一部分的数据范围,s2,e2表示第二部分的数据范围//两个部分的数据分别是排序好了的,要将两个部分的数据进行合并int s1=left;int e1=mid;int s2=mid+1;int e2=right;//定义辅助数组help来帮助合并int[]help=new int[right-left+1];//放数据的时候有以下的几种情况//1.两个部分的数据还没有哪个部分全放到help数组中int k=0;    //k是用于指向help数组的下标while (s1<=e1&&s2<=e2){//当s1下标的数据比s2下标的小时,s1下标的数据就先放到help数组中if(arr[s1]<arr[s2]){help[k++]=arr[s1++];}else {help[k++]=arr[s2++];}}//2.s1>e1 第一部分的数据都放到了help数组中//直接将第二部分的数据全放到help数组中while (s2<=e2){help[k++]=arr[s2++];}//3.s2>e1 第二部分的数据都放到了help数组中//直接将第一部分的数据全放到help数组中while (s1<=e1){help[k++]=arr[s1++];}//此时两个部分的数据都放到了help数组中//将数组中对应部分的数据改为help数组中的数据(help数组中的数据是合并好了的)for(int i=left,j=0;i<=right;i++,j++){arr[i]=help[j];}}

代码及注释(非递归实现)
 

 //归并排序---非递归public static void mergeSortNo(int[] array){//一个数据为一组int gap=1;while (gap<array.length){for(int i=0;i<array.length;i+=2*gap){int left=i;int mid=left+gap-1;int right=mid+gap;merge(array,left,mid,right);}gap=gap*2;}} //合并private static void merge(int[] array,int left,int mid,int right){int s1=left;int e1=mid;int s2=mid+1;int e2=right;//定义辅助数组int[]help=new int[right-left+1];int k=0;//两组数据都没放完while (s1<=e1&&s2<=e2){if(array[s1]<array[s2]){help[k++]=array[s1++];}else {help[k++]=array[s2++];}}//当有一组中的数据放完while (s1<=e1){help[k++]=array[s1++];}while (s2<=e2){help[k++]=array[s2++];}//将合并好的数据返回给数组arrayfor (int i=0;i<help.length;i++){array[left+i]=help[i];}}

相关文章:

排序算法-归并排序

属性 归并排序&#xff08;MERGE-SORT&#xff09;是建立在归并操作上的一种有效的排序算法,该算法是采用分治法&#xff08;Divide and Conquer&#xff09;的一个非常典型的应用。将已有序的子序列合并&#xff0c;得到完全有序的序列&#xff1b;即先使每个子序列有序&#…...

vue3 整合 springboot 打完整jar包

前端 .env.developmen VITE_APP_BASE_URL/api.env.production VITE_APP_BASE_URL/axios 配置 axios.defaults.baseURL import.meta.env.VITE_APP_BASE_URLpackage.json "scripts": {"dev": "vite --mode development","build": &…...

依赖倒转原则是什么?

依赖倒转原则&#xff08;Dependency Inversion Principle&#xff09;是面向对象设计中的另一个基本原则&#xff0c;它是由Robert C. Martin提出的&#xff0c;它的中心思想是面向接口编程&#xff0c;该原则指出高层模块不应该依赖于低层模块&#xff0c;两者都应该依赖于抽…...

什么是GPT与MBR

GPT&#xff08;GUID Partition Table&#xff09;和MBR&#xff08;Master Boot Record&#xff09;是两种不同的磁盘分区表格式。 MBR是一种较早的磁盘分区表格式&#xff0c;它使用512字节的扇区作为存储空间。MBR分区表可以定义最多4个主分区&#xff0c;每个主分区都可以…...

前后端开发接口联调对接参数

前言 一个完整的互联网系统项目,需要前后端配合,进行上线,针对前端开发者,现在互联网主流的项目都是前后端分离 也就是后端负责提供数据接口,前端负责UI界面数据渲染 凡是在前台数据展示与用户交互的,都是由前端来实现的,而数据来源是由后台服务提供的 在浏览器c端能够发送后端…...

定时任务框架-xxljob

1.定时任务 spring传统的定时任务Scheduled&#xff0c;但是这样存在这一些问题 &#xff1a; 做集群任务的重复执行问题 cron表达式定义在代码之中&#xff0c;修改不方便 定时任务失败了&#xff0c;无法重试也没有统计 如果任务量过大&#xff0c;不能有效的分片执行 …...

idea项目配置三大步

场景&#xff1a; 使用 idea 打开一个新项目的时候&#xff0c;想让项目迅速跑起来&#xff0c; 其实只需要下面简单三步&#xff1a; 1. 首先&#xff0c;配maven 2. 其次&#xff0c;配置 jdk 这里配置 project 就行了&#xff0c;不用管Modules中的配置。 3. 最后&#…...

学会SpringMVC之自定义注解各种场景应用,提高开发效率及代码质量

目录 一、简介 ( 1 ) 是什么 ( 2 ) 分类 ( 3 ) 作用 二、自定义注解 ( 1 ) 如何自定义注解 ( 2 ) 场景演示 场景一&#xff08;获取类与方法上的注解值&#xff09; 场景二&#xff08; 获取类属性上的注解属性值 &#xff09; 场景三&#xff08; 获取参数修…...

步态识别常见模块解读及代码实现:基于OpenGait框架

步态识别常见模块解读及代码实现&#xff1a;基于OpenGait框架 最近在看步态识别相关论文&#xff0c;但是因为记忆力下降的原因&#xff0c;老是忘记一些内容。因此记录下来方便以后查阅&#xff0c;仅供自己学习参考&#xff0c;没有背景知识和论文介绍。 目录 步态识别常见…...

前端八股文之“闭包”

一、定义 一句话概括闭包&#xff1a;能够访问函数内部变量的函数与这个变量的组合构成了闭包结构。如下代码 function fuc1(){let num 999return function fuc2(){console.log(num)}}fuc1()(); 如代码所示&#xff0c;fuc2和父级变量num构成了一个闭包环境。 二、原理 子…...

数据可视化:掌握数据领域的万金油技能

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ 🐴作者:秋无之地 🐴简介:CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作,主要擅长领域有:爬虫、后端、大数据开发、数据分析等。 🐴欢迎小伙伴们点赞👍🏻、收藏⭐️、…...

Apache Kafka 基于 S3 的数据导出、导入、备份、还原、迁移方案

在系统升级或迁移时&#xff0c;用户常常需要将一个 Kafka 集群中的数据导出&#xff08;备份&#xff09;&#xff0c;然后在新集群或另一个集群中再将数据导入&#xff08;还原&#xff09;。通常&#xff0c;Kafka集群间的数据复制和同步多采用 Kafka MirrorMaker&#xff0…...

事务管理AOP

事务管理 事务回顾 概念&#xff1a;事务是一组操作的集合&#xff0c;它是一个不可分割的工作单位&#xff0c;这些操作要么同时成功&#xff0c;要么同时失败 操作&#xff1a; 开启事务&#xff1a;一组操作开始前&#xff0c;开启事务&#xff0d;start transaction/be…...

Java从Tif中抽取最大的那张图进行裁剪成x*y份

之前我有一篇帖子《kfb格式文件转jpg格式》讲述到 kfb > tif > jpg&#xff0c;但是针对于超大tif中的大图是无法顺利提取的&#xff0c;就算是能顺利提取&#xff0c;试想一下&#xff0c;2G的tif文件&#xff0c;如果能提取处理最大的那张图&#xff0c;并且在不压缩的…...

人工智能AI界的龙头企业,炸裂的“英伟达”时代能走多远

原创 | 文 BFT机器人 1、AI芯片的竞争格局已趋白热化 尽管各类具有不同功能和定位的AI芯片在一定程度上可实现互补&#xff0c;但同时也在机遇与挑战并存中持续调整定位。在AI训练端&#xff0c;英伟达的GPU凭着高算力的门槛&#xff0c;一直都是训练端的首选。 只有少数芯片能…...

【实战】H5 页面同时适配 PC 移动端 —— 旋转横屏

文章目录 一、场景二、方案三、书单推荐01 《深入实践Kotlin元编程》02 《Spring Boot学习指南》03 《Kotlin编程实战》 一、场景 一个做数据监控的单页面&#xff0c;页面主要内容是一个整体必须是宽屏才能正常展示&#xff0c;这时就不能用传统的适配方案了&#xff0c;需要…...

使用凌鲨进行聚合搜索

作为研发人员&#xff0c;我们经常需要在多个来源之间查找信息&#xff0c;以便进行研发工作。除了常用的搜索引擎如百度和必应之外&#xff0c;我们还需要查阅各种代码文档和依赖包等资源。这些资源通常分散在各个网站和文档库中&#xff0c;需要花费一定的时间和精力才能找到…...

程序设计之——手把手教你如何从Excel文件中读取学生信息

在当今信息化时代&#xff0c;计算机技术已经深入到各个领域&#xff0c;而程序设计则成为推动信息化建设的关键技术之一。在众多领域中&#xff0c;学生信息管理系统无疑是其中一个重要的应用。本文将从学生信息管理系统的开发入手&#xff0c;探讨开如何高效且保证质量的完成…...

Docker容器化技术(从零学会Docker)

文章目录 前言一、初识Docker1.初识Docker-Docker概述2.初识Docker-安装Docker3.初识Docker-Docker架构4.初识Docker-配置镜像加速器 二、Docker命令1.Docker命令-服务相关命令2.Docker命令-镜像相关命令3.Docker命令-容器相关命令 三、Docker容器的数据卷1.Docker容器数据卷-数…...

【新版】系统架构设计师 - 案例分析 - 总览

个人总结&#xff0c;仅供参考&#xff0c;欢迎加好友一起讨论 架构 - 案例分析 - 总览 新旧大纲对应 旧版新版系统规划软件架构设计设计模式系统设计系统建模分布式系统设计嵌入式系统设计系统的可靠性分析与设计系统的安全性和保密性设计系统计划信息系统架构的设计理论和实…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...