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

算法通关村第十关 | 归并排序

1. 归并排序原理

        归并排序(MERARE-SORT)简单来说就是将大的序列先视为若干个比较小的数组,分成比较小的结构,然后是利用归并的思想实现的排序方法,该算法采用经典的分治策略(分就是将问题分成一些小的问题分别求解,而治则将分的阶段得到的各答案“合”在一起)。

        归并排序算法就是应用归并思想的一个典型例子。在归并排序中,我们首先将未排序的数组不断地划分成两个子数组,直到子数组的长度为1。然后,我们合并子数组,使得子数组按照排序规则排列,最后得到排序完成的数组。

        分治法可以看作是"分而治之"的意思,也就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,从而使得原问题的解即子问题的解的合并。

都需要递归地解决子问题,并在最后合并子问题的解。

  1. 上图就是将 一个大的数组二分成一个个小的数组,知道最后每个划分的数组只有一个元素的时候,开始进行合并,这种操作就是分阶段,可以理解为递归拆分子序列的过程,递归的深度为logn。
  2. 治阶段,将两个已经有序的子序列合并成一个有序序列。

遍历时处理元素的过程:

 总结归并排序的思路:

  • 首先将原数组二分的拆分,直到最后问题变成最小的时候,也就是每个子数组只有一个元素,开始进行第二步。
  • 将两个子数组合并,按照合并两个有序数组的方式进行,按照图中每个左右子树从下往上,然后再将左右子树合并,每个子树最后都是一个有序数组。
    public static void mergeSort(int[] array, int start, int end, int temp[]){if (start >= end){return;}mergeSort(array, start, (start + end) / 2,temp);mergeSort(array, (start + end) / 2 + 1, end,temp);merge(array, start, end, temp);}public static void merge(int[] array, int start, int end, int[] temp){int middle = (start + end) /2;int left = start;int right = middle + 1;int index = left;//将两边的最小元素移到左边while (left <= middle && right <= end){if (array[left] < array[right]){temp[index++] = array[left++];}else {temp[index++] = array[right++];}}//左端元素遍历完,依次把右端元素转移过来while (left <= middle){temp[index++] = array[left++];}//左端元素遍历完,依次把右端元素转移过来while (right <= end){temp[index++] = array[right++];}//将temp中的元素依次转到array中,for (int i = start; i <= end; i++){array[i] = temp[i];}}

相关文章:

算法通关村第十关 | 归并排序

1. 归并排序原理 归并排序&#xff08;MERARE-SORT&#xff09;简单来说就是将大的序列先视为若干个比较小的数组&#xff0c;分成比较小的结构&#xff0c;然后是利用归并的思想实现的排序方法&#xff0c;该算法采用经典的分治策略&#xff08;分就是将问题分成一些小的问题分…...

SpringBoot3集成Kafka

标签&#xff1a;Kafka3.Kafka-eagle3&#xff1b; 一、简介 Kafka是一个开源的分布式事件流平台&#xff0c;常被用于高性能数据管道、流分析、数据集成和关键任务应用&#xff0c;基于Zookeeper协调的处理平台&#xff0c;也是一种消息系统&#xff0c;具有更好的吞吐量、内…...

css学习1

1、样式定义如何显示元素。 2、样式通常保存至外部的css文件中。 3、样式可以使内容与表现分离。 4、css主要有两部分组成&#xff1a;选择器与一条或多条声明。 选择器通常为要改变的html元素&#xff0c;每条声明由一个属性和一个值组成。每个属性有一个值&#xff0c;属性…...

rust踩雷笔记(1)——切片传参和解引用赋值

最近学习rust&#xff0c;网上资料还是很有限&#xff0c;做题遇到的问题&#xff0c;有时需要自己试验。把自己做题过程遇到的问题&#xff0c;和试验的结论&#xff0c;做一些简单记录。 阅读下列文字和代码 用切片&#xff08;的引用&#xff09;做参数要非常小心&#xff…...

安全 1自测

常见对称加密算法&#xff1a; DES&#xff08;Data Encryption Standard&#xff09;&#xff1a;数据加密标准&#xff0c;速度较快&#xff0c;适用于加密大量数据的场合&#xff1b; 3DES&#xff08;Triple DES&#xff09;&#xff1a;是基于DES&#xff0c;对一块数据用…...

寻路算法小游戏

寻路算法小demo 寻路算法有两种&#xff0c;一种是dfs 深度优先算法&#xff0c;一种是 dfs 深度优先算法 深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义&#xff0c;深度优先&#xff0c;则是以深度为准则&#xff0c;先一条路走到底&#xff0c;直到达到目标。这…...

CSS基础 知识点总结

一.CSS简介 1.1 CSS简介 ① CSS指的是层叠样式表&#xff0c;用来控制网页外观的一门技术 ② CSS发展至今&#xff0c;经历过CSS1.0 CSS2.0 CSS2.1 CSS3.0这几个版本&#xff0c;CSS3.0是CSS最新版本 1.2 CSS引入方式 ① 在一个页面引入CSS&#xff0c;共有三种方式 外部…...

自动执行探索性数据分析 (EDA),更快、更轻松地理解数据

一、说明 EDA是 exploratory data analysis (探索性数据分析 )的缩写。所谓EDA就是在数据分析之前需要对数据进行以此系统性研判&#xff0c;在这个研判后&#xff0c;得到基本的数据先验知识&#xff0c;在这个基础上进行数据分析。本文将在R语言和python语言的探索性处理。 摄…...

【自定义系统服务】【android13】添加自定义java系统服务

背景 在平时的业务开发中,我们往往需要开发自定义的系统服务来处理自己特殊的需求,这里介绍的是添加自定义的Java系统服务,可以在系统App中直接调用 定义aidl Binder默认可以传输基本类型的数据,如果要传递类对象,则这个类需要实现序列化。我们先定义一个序列化的自定义…...

【Sklearn】基于随机梯度下降算法的数据分类预测(Excel可直接替换数据)

【Sklearn】基于随机梯度下降算法的数据分类预测(Excel可直接替换数据) 1.模型原理2.模型参数3.文件结构4.Excel数据5.下载地址6.完整代码7.运行结果1.模型原理 随机梯度下降(Stochastic Gradient Descent,SGD)是一种优化算法,用于训练模型的参数以最小化损失函数。在分…...

44、TCP报文(二)

接上节内容&#xff0c;本节我们继续TCP报文首部字段含义的学习。上节为止我们学习到“数据偏移”和“保留”字段。接下来我们学习后面的一些字段&#xff08;暂不包含“检验和”的计算方法和选项字段&#xff09;。 TCP首部结构&#xff08;续&#xff09; “数据偏移”和“保…...

目标检测(Object Detection)

文章目录 1. 目标检测1.1 目标检测简要概述及名词解释1.2 IOU1.3 TP TN FP FN1.4 precision&#xff08;精确度&#xff09;和recall&#xff08;召回率&#xff09; 2. 边框回归Bounding-Box regression3. Faster R-CNN3.1 Faster-RCNN&#xff1a;conv layer3.2 Faster-RCNN&…...

vue中实现文字检索时候将搜索内容标红

实现结果 html&#xff1a; <div class"searchBox"><span class"bt">标&#8195&#8195题</span><div class"search"><div class"shuru"><!-- <span class"title">生产经营<…...

PCL protocol composition logic

PCL 协议组合逻辑 一 主体&#xff08;principal&#xff09;和线程&#xff08;thread&#xff09;的区分 1.主体&#xff1a;指 **协议的参与者&#xff0c;用X^来表示。**每个主体可以扮演一个或多个角色&#xff0c;如 InitCR和RespCR &#xff1b; 2.线程&#xff1a;主…...

聊聊看React和Vue的区别

Vue 更适合小项目&#xff0c;React 更适合大公司大项目&#xff1b; Vue 的学习成本较低&#xff0c;很容易上手&#xff0c;但项目质量不能保证...... 真的是这样吗&#xff1f;借助本篇文章&#xff0c;我们来从一些方面的比较来客观的去看这个问题。 论文档的丰富性 从两个…...

OSPF在广播类型的网络拓扑中DR和BDR的选举

指定路由器&#xff08;DR&#xff09;&#xff1a; 一个网段上的其他路由器都和指定路由器&#xff08;DR&#xff09;构成邻接关系&#xff0c;而不是它们互相之间构成邻接关系。 备份指定路由器&#xff08;BDR&#xff09;&#xff1a; 当DR出现问题&#xff0c;由BDR接…...

系统学习Linux-Mariadb高可用MHA

概念 MHA&#xff08;MasterHigh Availability&#xff09;是一套优秀的MySQL高可用环境下故障切换和主从复制的软件。 MHA 的出现就是解决MySQL 单点的问题。 MySQL故障切换过程中&#xff0c;MHA能做到0-30秒内自动完成故障切换操作。 MHA能在故障切换的过程中最大程度上…...

慢SQL的原因

如何排查慢SQL问题 识别慢SQL&#xff1a;使用数据库性能监控工具&#xff0c;如慢SQL日志&#xff0c;识别耗时较长的查询。执行计划分析&#xff1a;使用数据库提供的分析工具&#xff0c;例如EXPLAIN来查看查询的执行计划&#xff0c;判断是否存在全表扫描&#xff0c;索引…...

php正则替换文章的图片

要使用正则表达式替换文章中的图片链接&#xff0c;可以按照以下步骤进行操作&#xff1a; 1. 获取文章内容&#xff1a;首先&#xff0c;你需要获取包含图片链接的文章内容。你可以从文件中读取文章&#xff0c;或者从数据库中检索文章内容。 2. 使用正则表达式匹配图片链接…...

57 | TAPTAP客户端分析

TAPTAP客户端分析 一、用户群分析 首先,TapTap用户群可分为三大类: 游戏爱好者游戏发烧者游戏开发者(次要用户,有开发者后台,可以显示数据,不重点分析)注:爱好者与发烧者区别在于,前者是用空余时间来玩游戏,时间不如后者充足,且后者更执着于游戏,游戏种类更多。 …...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

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

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

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...