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

归并排序 和 七大算法的总结图

目录

什么是递归排序:

        图解:

递归方法:

    代码实现:

        思路分析:

       非递归方法:

       思路:

       代码实现:

        思路分析:


什么是递归排序:

        先将数据分解成诺干个序列,将子序列合并排序,得到有序的序列,再与旁边子序列合并;即先使每个子序列有序,再使子序列段间有序。最后将两个有序表合并成⼀个有序表。

        图解:

        

         

递归方法:

    代码实现

public static void mergeSort(int[] arr) {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,mid,right);}private static void merge(int[] arr, int left, int mid, int right) {//临时数组int[] tmpArr = new int[right - left + 1];int k = 0;int s1 = left;int e1 = mid;int s2 = mid + 1;int e2 = right;while(s1 <= e1 && s2 <= e2) {if(arr[s1] <= arr[s2]) {tmpArr[k++] = arr[s1++];}else {tmpArr[k++] = arr[s2++];}}while(s1 <= e1) {tmpArr[k++] = arr[s1++];}while(s2 <= e2) {tmpArr[k++] = arr[s2++];}//拷贝临时数组给到arrfor (int i = 0; i < k; i++) {arr[i + left] = tmpArr[i];}}

        思路分析

        

         与快速排序类似,结合上图,定义一个 mid 作为 一段数据的中间下标,然后依次往下分,左边的新 left 和 right 为上一个段数据的 left 和 mid ,右边的新 left 和 right 为上一个段数据的 mid + 1 和 right。分解结束条件为 当 left 与 right 相遇了

        对于merge方法,结合此图:

        

         此图是原数据的左边的一段数据,定义一个临时数组,把下面的两个已经有序的 一段数据合并成给到临时数组,方法是s1 与 s2 比较,哪个小先给到临时数组,直到一方为放完。之后,把没放完的一方全部给到临时数组。k就得到临时数组的元素个数。

        最后,通过for循环把临时数组的数据拷贝到原始数组里,但是有个要注意的地方:

        

         看蓝色圈出来的区域,3 9 4 2 的那段数据的 3 和 9 一段小数据,如果merge方法 的for循环是这样的:

 for (int i = 0; i < k; i++) {arr[i] = tmpArr[i];}

        那么临时数组的数据拷贝到原始数组里,会出现问题。

        原始数组的 元素3 下标应该是 4,如果按照从 0 下标开始,  会给到原始数组 0 下标位置这样是不对的,但如果加上了 left:

 for (int i = 0; i < k; i++) {arr[i + left] = tmpArr[i];}

        这样就能确保 元素3 给到了 原始数组 4 下标的位置。

        

       非递归方法:

       思路:

        

          上图对于8个原数据,我们先把数据从 1个1个有序(6和10,1和7,3和9,2和4),一直到 2个2个 有序((6   10和1   7 );(3   9 和 2   4) )来进行排序,那么最后 4个4个 有序((6   10   1   7 )和(3   9   2   4))就能完成排序了。

        首先定义了 i 作为遍历数组使用,l 作为 左边起始,r 作为结束位置,m 是 他们的中间位置。

        定义一个 gap 作为 临界值,初始化为1,循环结束 gap 每次 乘以 2 ,当 gap 为 数组长度时不进入循环。

        上图是 gap 为 2 的时候,其他参数赋值如上图。

       代码实现

public static void feidigui(int[] arr) {int gap = 1;while(gap < arr.length) {for (int i = 0; i < arr.length; i = i + 2*gap) {int left = i;int mid = left + gap - 1;if(mid >= arr.length) {mid = arr.length-1;}int right = mid+gap;if(right >= arr.length) {right = arr.length-1;}merge(arr,left,mid,right);}gap *= 2;}}private static void merge(int[] arr, int left, int mid, int right) {//临时数组int[] tmpArr = new int[right - left + 1];int k = 0;int s1 = left;int e1 = mid;int s2 = mid + 1;int e2 = right;while(s1 <= e1 && s2 <= e2) {if(arr[s1] <= arr[s2]) {tmpArr[k++] = arr[s1++];}else {tmpArr[k++] = arr[s2++];}}while(s1 <= e1) {tmpArr[k++] = arr[s1++];}while(s2 <= e2) {tmpArr[k++] = arr[s2++];}//拷贝临时数组给到arrfor (int i = 0; i < k; i++) {arr[i + left] = tmpArr[i];}}

        思路分析

        

         结合代码和此图,当 gap 为 2 时,i 下一次取值为 i + 2*gap,确保后面的(3   9   2   4)也能进行有序排列。

        要注意的是:

        

         过程可能会出现上面三种情况,当 mid 超过了 数组长度 ,就越界了,就要把 mid 设置为数组的最后一个位置,right 同理。此过程不会影响 merge 方法的出现错误。(相当于处理边界值)

        

        归并排序是稳定的。

        

      七大算法的总结图:

        

相关文章:

归并排序 和 七大算法的总结图

目录 什么是递归排序&#xff1a; 图解&#xff1a; 递归方法&#xff1a; 代码实现&#xff1a; 思路分析&#xff1a; 非递归方法&#xff1a; 思路&#xff1a; 代码实现&#xff1a; 思路分析&#xff1a; 什么是递归排序&#xff1a; 先将数据分解成诺干个序列&#xff0…...

嵌入式硬件篇---原码、补码、反码

文章目录 前言简介八进制原码、反码、补码1. 原码规则示例问题 2. 反码规则示例问题 3. 补码规则示例优点 4. 补码的运算5. 总结 十六进制原码、反码、补码1. 十六进制的基本概念2. 十六进制的原码规则示例 3. 十六进制的反码规则示例 4. 十六进制的补码规则示例 5. 十六进制补…...

评估多智能体协作网络(MACNET)的性能:COT和AUTOGPT基线方法

评估多智能体协作网络(MACNET)的性能 方法选择:选择COT(思维链,Chain of Thought)、AUTOGPT等作为基线方法。 COT是一种通过在推理过程中生成中间推理步骤,来增强语言模型推理能力的方法,能让模型更好地处理复杂问题,比如在数学问题求解中,展示解题步骤。 AUTOGPT则是…...

洛谷题目: P2398 GCD SUM 题解 (本题较难,省选-难度)

题目传送门&#xff1a; P2398 GCD SUM - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 前言&#xff1a; 本题涉及到 欧拉函数&#xff0c;素数判断&#xff0c;质数&#xff0c;筛法 &#xff0c;三大知识点&#xff0c;相对来说还是比较难的。 本题要求我们计算 …...

kubernetes-cni 框架源码分析

深入探索 Kubernetes 网络模型和网络通信 Kubernetes 定义了一种简单、一致的网络模型&#xff0c;基于扁平网络结构的设计&#xff0c;无需将主机端口与网络端口进行映射便可以进行高效地通讯&#xff0c;也无需其他组件进行转发。该模型也使应用程序很容易从虚拟机或者主机物…...

AI Agent有哪些痛点问题

AI Agent有哪些痛点问题 目录 AI Agent有哪些痛点问题AI Agent领域有哪些知名的论文缺乏一个将智能多智能体技术和在真实环境中学习的两个适用流程结合起来的统一框架LLM的代理在量化和客观评估方面存在挑战自主代理在动态环境中学习、推理和驾驭不确定性存在挑战AI Agent领域有…...

使用Java爬虫获取京东JD.item_sku API接口数据

在电商领域&#xff0c;商品的SKU&#xff08;Stock Keeping Unit&#xff09;信息是运营和管理的关键数据。SKU信息包括商品的规格、价格、库存等&#xff0c;对于商家的库存管理、定价策略和市场分析至关重要。京东作为国内领先的电商平台&#xff0c;提供了丰富的API接口&am…...

华为云+硅基流动使用Chatbox接入DeepSeek-R1满血版671B

华为云硅基流动使用Chatbox接入DeepSeek-R1满血版671B 硅基流动 1.1 注册登录 1.2 实名认证 1.3 创建API密钥 1.4 客户端工具 OllamaChatboxCherry StudioAnythingLLM 资源包下载&#xff1a; AI聊天本地客户端 接入Chatbox客户端 点击设置 选择SiliconFloW API 粘贴1.3创…...

平方数列与立方数列求和的数学推导

先上结论&#xff1a; 平方数列求和公式为&#xff1a; S 2 ( n ) n ( n 1 ) ( 2 n 1 ) 6 S_2(n) \frac{n(n1)(2n1)}{6} S2​(n)6n(n1)(2n1)​ 立方数列求和公式为&#xff1a; S 3 ( n ) ( n ( n 1 ) 2 ) 2 S_3(n) \left( \frac{n(n1)}{2} \right)^2 S3​(n)(2n(n1)​…...

Java中的synchronized关键字与锁升级机制

在多线程编程中&#xff0c;线程同步是确保程序正确执行的关键。当多个线程同时访问共享资源时&#xff0c;如果不进行同步管理&#xff0c;可能会导致数据不一致的问题。为了避免这些问题&#xff0c;Java 提供了多种同步机制&#xff0c;其中最常见的就是 synchronized 关键字…...

告别传统校准!GNSS模拟器在计量行业的应用

随着GNSS技术的不断进步&#xff0c;各类设备广泛采用该技术实现高精度定位&#xff0c;并推动了其在众多领域的广泛应用。对于关键行业如汽车制造和基础设施&#xff0c;设备的可用性和可靠性被视为基本准则&#xff0c;GNSS作为提供“绝对位置”信息的关键传感器&#xff0c;…...

数据结构结尾

1.二叉树的分类 搜索二叉树&#xff0c;平衡二叉树&#xff0c;红黑树&#xff0c;B树&#xff0c;B树 2.Makefile文件管理 注意&#xff1a; 时间戳&#xff1a;根据时间戳&#xff0c;只编译发生修改后的文件 算法&#xff1a; 算法有如上五个要求。 算法的时间复杂度&am…...

【golang】量化开发学习(一)

均值回归策略简介 均值回归&#xff08;Mean Reversion&#xff09;假设价格会围绕均值波动&#xff0c;当价格偏离均值一定程度后&#xff0c;会回归到均值。 基本逻辑&#xff1a; 计算一段时间内的移动均值&#xff08;如 20 天均线&#xff09;。当当前价格高于均值一定比…...

AI前端开发:跨领域合作的新引擎

随着人工智能技术的飞速发展&#xff0c;AI代码生成器等工具的出现正深刻地改变着软件开发的模式。 AI前端开发的兴起&#xff0c;不仅提高了开发效率&#xff0c;更重要的是促进了跨领域合作&#xff0c;让数据科学家、UI/UX设计师和前端工程师能够更紧密地协同工作&#xff0…...

数组练习(深入理解、实践数组)

1.练习1&#xff1a;多个字符从两端移动&#xff0c;向中间汇聚 编写代码&#xff0c;演示多个字符从两端移动&#xff0c;向中间汇聚 #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<string.h> int main() {//解题思路&#xff1a;//根据题意再…...

Bigemap Pro如何进行面裁剪

一般在处理矢量数据&#xff0c;制图过程中&#xff0c;常常会用到面文件的裁剪功能&#xff0c;那么有没有一个工具可以同时实现按照线、顶点、网格以及面来裁剪呢&#xff1f;今天给大家介绍一个宝藏工具&#xff0c;叫做Bigemap Pro&#xff0c;在这里工具里面可以实现上述面…...

acwing算法全总结-数学知识

快速幂 原题链接&#xff1a;快速幂 ac代码&#xff1a; #include<iostream> #include<algorithm> using namespace std; typedef long long LL; LL qmi(int a,int b,int p) {LL res1%p;while(b)//这里本应该分两次进行&#xff0c;不过只有一次询问{if(b&1)…...

SpringMVC学习使用

一、SpringMVC简单理解 1.1 Spring与Web环境集成 1.1.1 ApplicationContext应用上下文获取方式 应用上下文对象是通过new ClasspathXmlApplicationContext(spring配置文件) 方式获取的&#xff0c;但是每次从容器中获得Bean时都要编写new ClasspathXmlApplicationContext(sp…...

10、《文件上传与下载:MultipartFile与断点续传设计》

文件上传与下载&#xff1a;MultipartFile与断点续传设计 一、基础文件上传与MultipartFile解析 1.1 Spring MVC文件上传基础 PostMapping("/upload") public String handleFileUpload(RequestParam("file") MultipartFile file) {if (!file.isEmpty())…...

DeepSeek 本地部署(电脑安装)

1.先安装Ollama 开源框架 网址链接为:Ollama 2.点中间的下载 3.选系统 4.下载好就安装 5.输入命令ollama -v 6.点击Model 7.选如下 8.选版本 9.复杂对应命令 10.控制台粘贴下载 11.就可以问问题啦 12.配置UI界面(在扩展里面输入) 13.配置完即可打开 14.选择刚才安装的就好啦…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...