归并排序 和 七大算法的总结图
目录
什么是递归排序:
图解:
递归方法:
代码实现:
思路分析:
非递归方法:
思路:
代码实现:
思路分析:
什么是递归排序:
先将数据分解成诺干个序列,将子序列合并排序,得到有序的序列,再与旁边子序列合并;即先使每个子序列有序,再使子序列段间有序。最后将两个有序表合并成⼀个有序表。
图解:

递归方法:
代码实现:
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 方法的出现错误。(相当于处理边界值)
归并排序是稳定的。
七大算法的总结图:

相关文章:
归并排序 和 七大算法的总结图
目录 什么是递归排序: 图解: 递归方法: 代码实现: 思路分析: 非递归方法: 思路: 代码实现: 思路分析: 什么是递归排序: 先将数据分解成诺干个序列࿰…...
嵌入式硬件篇---原码、补码、反码
文章目录 前言简介八进制原码、反码、补码1. 原码规则示例问题 2. 反码规则示例问题 3. 补码规则示例优点 4. 补码的运算5. 总结 十六进制原码、反码、补码1. 十六进制的基本概念2. 十六进制的原码规则示例 3. 十六进制的反码规则示例 4. 十六进制的补码规则示例 5. 十六进制补…...
评估多智能体协作网络(MACNET)的性能:COT和AUTOGPT基线方法
评估多智能体协作网络(MACNET)的性能 方法选择:选择COT(思维链,Chain of Thought)、AUTOGPT等作为基线方法。 COT是一种通过在推理过程中生成中间推理步骤,来增强语言模型推理能力的方法,能让模型更好地处理复杂问题,比如在数学问题求解中,展示解题步骤。 AUTOGPT则是…...
洛谷题目: P2398 GCD SUM 题解 (本题较难,省选-难度)
题目传送门: P2398 GCD SUM - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 前言: 本题涉及到 欧拉函数,素数判断,质数,筛法 ,三大知识点,相对来说还是比较难的。 本题要求我们计算 …...
kubernetes-cni 框架源码分析
深入探索 Kubernetes 网络模型和网络通信 Kubernetes 定义了一种简单、一致的网络模型,基于扁平网络结构的设计,无需将主机端口与网络端口进行映射便可以进行高效地通讯,也无需其他组件进行转发。该模型也使应用程序很容易从虚拟机或者主机物…...
AI Agent有哪些痛点问题
AI Agent有哪些痛点问题 目录 AI Agent有哪些痛点问题AI Agent领域有哪些知名的论文缺乏一个将智能多智能体技术和在真实环境中学习的两个适用流程结合起来的统一框架LLM的代理在量化和客观评估方面存在挑战自主代理在动态环境中学习、推理和驾驭不确定性存在挑战AI Agent领域有…...
使用Java爬虫获取京东JD.item_sku API接口数据
在电商领域,商品的SKU(Stock Keeping Unit)信息是运营和管理的关键数据。SKU信息包括商品的规格、价格、库存等,对于商家的库存管理、定价策略和市场分析至关重要。京东作为国内领先的电商平台,提供了丰富的API接口&am…...
华为云+硅基流动使用Chatbox接入DeepSeek-R1满血版671B
华为云硅基流动使用Chatbox接入DeepSeek-R1满血版671B 硅基流动 1.1 注册登录 1.2 实名认证 1.3 创建API密钥 1.4 客户端工具 OllamaChatboxCherry StudioAnythingLLM 资源包下载: AI聊天本地客户端 接入Chatbox客户端 点击设置 选择SiliconFloW API 粘贴1.3创…...
平方数列与立方数列求和的数学推导
先上结论: 平方数列求和公式为: S 2 ( n ) n ( n 1 ) ( 2 n 1 ) 6 S_2(n) \frac{n(n1)(2n1)}{6} S2(n)6n(n1)(2n1) 立方数列求和公式为: S 3 ( n ) ( n ( n 1 ) 2 ) 2 S_3(n) \left( \frac{n(n1)}{2} \right)^2 S3(n)(2n(n1)…...
Java中的synchronized关键字与锁升级机制
在多线程编程中,线程同步是确保程序正确执行的关键。当多个线程同时访问共享资源时,如果不进行同步管理,可能会导致数据不一致的问题。为了避免这些问题,Java 提供了多种同步机制,其中最常见的就是 synchronized 关键字…...
告别传统校准!GNSS模拟器在计量行业的应用
随着GNSS技术的不断进步,各类设备广泛采用该技术实现高精度定位,并推动了其在众多领域的广泛应用。对于关键行业如汽车制造和基础设施,设备的可用性和可靠性被视为基本准则,GNSS作为提供“绝对位置”信息的关键传感器,…...
数据结构结尾
1.二叉树的分类 搜索二叉树,平衡二叉树,红黑树,B树,B树 2.Makefile文件管理 注意: 时间戳:根据时间戳,只编译发生修改后的文件 算法: 算法有如上五个要求。 算法的时间复杂度&am…...
【golang】量化开发学习(一)
均值回归策略简介 均值回归(Mean Reversion)假设价格会围绕均值波动,当价格偏离均值一定程度后,会回归到均值。 基本逻辑: 计算一段时间内的移动均值(如 20 天均线)。当当前价格高于均值一定比…...
AI前端开发:跨领域合作的新引擎
随着人工智能技术的飞速发展,AI代码生成器等工具的出现正深刻地改变着软件开发的模式。 AI前端开发的兴起,不仅提高了开发效率,更重要的是促进了跨领域合作,让数据科学家、UI/UX设计师和前端工程师能够更紧密地协同工作࿰…...
数组练习(深入理解、实践数组)
1.练习1:多个字符从两端移动,向中间汇聚 编写代码,演示多个字符从两端移动,向中间汇聚 #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<string.h> int main() {//解题思路://根据题意再…...
Bigemap Pro如何进行面裁剪
一般在处理矢量数据,制图过程中,常常会用到面文件的裁剪功能,那么有没有一个工具可以同时实现按照线、顶点、网格以及面来裁剪呢?今天给大家介绍一个宝藏工具,叫做Bigemap Pro,在这里工具里面可以实现上述面…...
acwing算法全总结-数学知识
快速幂 原题链接:快速幂 ac代码: #include<iostream> #include<algorithm> using namespace std; typedef long long LL; LL qmi(int a,int b,int p) {LL res1%p;while(b)//这里本应该分两次进行,不过只有一次询问{if(b&1)…...
SpringMVC学习使用
一、SpringMVC简单理解 1.1 Spring与Web环境集成 1.1.1 ApplicationContext应用上下文获取方式 应用上下文对象是通过new ClasspathXmlApplicationContext(spring配置文件) 方式获取的,但是每次从容器中获得Bean时都要编写new ClasspathXmlApplicationContext(sp…...
10、《文件上传与下载:MultipartFile与断点续传设计》
文件上传与下载: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.选择刚才安装的就好啦…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
