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

归并排序个人见解

归并排序个人见解

  • 思路实现
  • 代码实现
    • 题目

思路实现

归并排序属于分治算法,分治算法有三个步骤:

  1. 分:将问题划分为多个规模较小的子问题,这些子问题与原始问题相似。
  2. 治:递归地解决这些子问题。如果子问题足够小,可以直接求解。
  3. 合:将子问题的解合并为原始问题的解。

归并排序的重点主要是 合,合 的过程中就会直接排好序。(这里是从小到大排序)

在这里插入图片描述
我们来模拟一下合的过程。

在这里插入图片描述
首先合的两个序列,一定都已经是有序的了。(如果不理解这个“一定有序” 后面会说的,先理解怎么合并的)

在合的过程中,有一块临时数组,也就是图中这个空的空间。

此时需要三个下标,分别指向两个序列的头和 那份空的空间的头。
在这里插入图片描述
此时比较 下标 i 和 j 的 值,小的那个 赋给 临时空间的 k 坐标,然后 小的坐标 和 k 都自增1。

对于图中的情况,那么就是1 过去。
在这里插入图片描述
然后继续比较 下标 为 i 的值和 下标为 j 的值。

此时 j 小,所以 2 过去。
在这里插入图片描述
然后一直重复此效果,此时必定有一个序列先把自己的数字 放完了。

比如图中的情况。
在这里插入图片描述
最终 下标 i 会移动到序列的外部(当然其实他是指向了右边的那个2,因为这两个序列其实是连续的)

所以此时不能够再次比较了。
在这里插入图片描述
接下来我们就需要判断 i 和 j 谁是否在序列内,谁在序列内,就循环的将值放到数组内。

比如这时 只有 j 在序列内部,所以就循环的将值放到临时数组里面,直到 j 出去了。
在这里插入图片描述
此时就会发现数组 排序好了。


而为什么两个序列一定是有序的是因为 归并排序会使用递归,会先递到只有一个元素。

比如刚才的那个图
在这里插入图片描述
在这里插入图片描述
在递到 只有一个元素的时候,它一定是有序的,因为只有一个数字啊。

所以往下合并的时候就一定是 有序的。

代码实现

接下来我们来看看代码,看完代码你就会恍然大悟了,如果没有,那么你可以再次看一下前面的思路。

我们以题目为引入。

题目

给定你一个长度为 n n n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行,第一行包含整数 n n n

第二行包含 n n n 个整数(所有整数均在 1 ∼ 1 0 9 1 \sim 10^9 1109 范围内),表示整个数列。

输出格式

输出共一行,包含 n n n 个整数,表示排好序的数列。

数据范围

1 ≤ n ≤ 100000 1 \le n \le 100000 1n100000

输入样例:

5
3 1 2 4 5

输出样例:

1 2 3 4 5

首先是准备阶段:
在这里插入图片描述
其中 题目当中 n 最大为 10的五次方,所以开辟这么大的数组。

这个tem为临时数组。

接着输入环节:
在这里插入图片描述
然后把归并排序封装成一个函数,最后直接输出。
在这里插入图片描述
对于归并排序函数来说,参数是 要排序的数组 和 要排序的区间头和区间尾。

在这里插入图片描述
还记得刚才的分治算法的三个步骤吗?

分、治、合。

首先是分,将问题分为多个子问题。
在这里插入图片描述
然后是治,递归处理子问题。

在这里插入图片描述
一想到递归,你就必须要考虑递归的结束条件,不能说让递归一直递下去。

在这里插入图片描述
所以我们需要在开头加上此语句。

这句话的意思,如果此时区间内没有元素或只有一个元素,就不需要往下递了。

分 和 治都完了,那么接下来就是 合 了。

还记得刚才的思路吗,首先我们需要创建三个坐标。
在这里插入图片描述
其中 下标 i 是 区间 [ l, mid ] 的头,下标 j 是 区间 [ mid+1, r ] 的头,k是 临时数组 tem 的头。

[ l, mid ] 和 [ mid+1, r ] 这两个区间也跟我们上边的递归的区间是一致的。

创建完之后,接下来就是循环比较 i 和 j 的值了。
在这里插入图片描述
在这里插入图片描述
循环直到 i 或者 j 的一个 跳出它的区间 后终止。

接着就需要 让还在 区间内部的 i 或者 j 走完整个区间。

在这里插入图片描述
在这里插入图片描述
此时临时数组内的值就一定全部有序了,接下来我们需要将这个临时数组的值 搬到我们的原数组中。

在这里插入图片描述
模拟完整过程:
在这里插入图片描述
在这里插入图片描述
完整代码如下:

#include <iostream>
using namespace std;const int N = 1e5+10;
int n;
int a[N], tem[N];void merge_sort(int q[], int l, int r)
{if (l >= r) return;int mid = (l + r) >> 1;merge_sort(q, l, mid), merge_sort(q, mid + 1, r);int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r){if (q[i] <= q[j]) tem[k++] = q[i++];else tem[k++] = q[j++];}while (i <= mid) tem[k++] = q[i++];while (j <= r) tem[k++] = q[j++];for (int i = l, k = 0; i <= r; i++, k++)q[i] = tem[k];}int main()
{scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &a[i]);merge_sort(a, 0, n-1);for (int i = 0; i < n; i++) printf("%d ", a[i]);return 0;
}

相关文章:

归并排序个人见解

归并排序个人见解 思路实现代码实现题目 思路实现 归并排序属于分治算法&#xff0c;分治算法有三个步骤&#xff1a; 分&#xff1a;将问题划分为多个规模较小的子问题&#xff0c;这些子问题与原始问题相似。治&#xff1a;递归地解决这些子问题。如果子问题足够小&#xf…...

软考初级网络管理员__网络单选题

1.观察交换机状态指示灯初步判断交换机故障&#xff0c;交换机运行中指示灯显示红色表示()。 警告 正常 待机 繁忙 2.通常测试网络连通性采用的命令是()。 Netstat Ping Msconfig Cmd 3.一台16端口的交换机可以产生&#xff08;&#xff09;个冲突域? 1 4 15 16…...

22.2 正则表达式-数据验证、数据变换

1. 数据验证 正则表达可用于验证文本是否满足某种给定的模式。 正则表达式也是一种语言&#xff0c;因此在使用之前必须先对其进行编译&#xff0c;并将编译结果保存在一个Regexp类型的变量里。以下两个函数即返回该变量的指针。 re, err : regexp.Compile("^[a-zA-Z0-…...

示例:WPF中应用DataGrid读取实体DisplayAttribute特性自动自动生成列名

一、目的&#xff1a;通过重写DataGrid的OnAutoGeneratingColumn方法实现根据定义特性自动生成列头信息功能 二、实现 <DataGrid ItemsSource"{local:GetStudents Count50}"/>实体定义如下 public class Student{[DataGridColumn("*")][Display(Na…...

八股文之JVM

目录 1.JVM内存划分 2.JVM类加载过程 3.JVM垃圾回收机制GC 3.1.判断谁是垃圾 3.2.如何释放对应的内存 1.JVM内存划分 在一个Java程序运行起来之后&#xff0c;jvm就会从操作系统中申请一块内存&#xff0c;然后就会将该内存划分成多个部分&#xff0c;用于不同的用途。 …...

给wordpress添加限制游客浏览数量功能

wordpress游客只可以浏览5个内容&#xff0c;其它更多的是的需要注册后才能浏览。以下是使用自定义代码来实现这一功能的基本步骤&#xff1a; 创建一个自定义角色&#xff1a; 使用wp_create_roles函数来创建一个名为“访客”的新角色。 该角色将只具有阅读权限。 限制文章…...

[二分枚举]特殊密码锁

描述 有一种特殊的二进制密码锁&#xff0c;由n个相连的按钮组成&#xff08;n<30&#xff09;&#xff0c;按钮有凹/凸两种状态&#xff0c;用手按按钮会改变其状态。 然而让人头疼的是&#xff0c;当你按一个按钮时&#xff0c;跟它相邻的两个按钮状态也会反转。当然&am…...

MT1434 找数字

题目 输入一个字符串(包含26个英文字母大小写及 . 空格&#xff0c;不含其他字符)&#xff0c;把其中连续的数字作为一个整数&#xff0c;依次存放到一个数组中&#xff0c;输出这些整数的和。 格式 输入格式 输入字符串 输出格式 输出整型 样例1 输入&#xff1a; a12…...

2024年6月四六级考试复盘

一、考试情况 1.1四级考试情况 听力&#xff1a;一开始没有进入状态。总共对了9道。7.1*37.1*314.2*3 8.2 新闻听力&#xff1a;3/7 长对话&#xff1a;3/8 讲座/讲话&#xff1a;3/10 阅读&#xff1a;3.55*7 7.1*8 14.2 * 7 181.05 选词填空&#xff1a;保守估计7/1…...

join和left join性能比较

1、join和left join性能比较&#xff08;AI生成&#xff09; 在MySQL中&#xff0c;JOIN和LEFT JOIN的效率并不是绝对的&#xff0c;它们之间的性能差异取决于多种因素&#xff0c;如表的大小、使用的索引、查询的复杂性等。 一般来说&#xff1a; 如果两个表之间的连接条件能…...

Qt正则表达式

需求&#xff1a;对输入的内容进行限制 只能以字母或下划线开始不能以数字开始 不能有中文 字母&#xff0c;数字&#xff0c;下划线混合使用 QRegExp rx("^[A-Za-z_][A-Za-z0-9_]*$");QRegExpValidator validator(rx);QLineEdit edit;edit.setValidator(&va…...

排序-快排算法对数组进行排序

目录 一、问题描述 二、解题思路 1.初始化 2.将右侧小于基准元素移到左边 3.将左侧大于基准元素移到右边 4.重复执行上面的操作 5.对分好的左、右分区再次执行分区操作 6.最终排序结果 三、代码实现 四、刷题链接 一、问题描述 二、解题思路 快排算法实现数组排序&am…...

flink学习-容错机制

checkpoint&#xff08;检查点&#xff09; 在flink中最重要的容错机制&#xff0c;就是checkpoint机制&#xff0c;使用checkpoint可以将之前某个时间点的所有的状态进行保存&#xff0c;这个存档就是checkpoint。 检查点的保存 周期性存储保存&#xff0c;间隔时间可以由用…...

InfluxDB技术分享

InfluxDB是一个开源的时间序列数据库&#xff0c;它被设计用来处理高速写入和查询大量的时间序列数据。以下是一份关于“InfluxDB在Java开发中的使用”的三十分钟技术分享内容概要&#xff1a; 1. 引言 (2分钟) 介绍时间序列数据和时间序列数据库的概念。引入InfluxDB的特点和…...

Windows10安装配置Docker客户端和WSL2与Hyper-V虚拟机

一、需求说明 需要在Windows系统中安装配置Docker的客户端,方便直接管理配置docker镜像容器内容。 二、Windows10安装Docker客户端步骤 2.1、下载安装Docker客户端 对于Windows 10以下的用户,推荐使用Docker Toolbox Windows安装文件:http://mirrors.aliyun.com/docker-…...

EIQ-ABC 分析法在配送中心储位分配中的应用

配送中心运作效率的高低主要取决于仓储业务流程的作业效率&#xff0c;在配送作业流程中&#xff0c;储位分配的是否合理性成为影响配送运作效率的重要因素。为实现储位的合理分配&#xff0c;提出通过对订单信息的分析&#xff0c;并应用 EIQ-ABC 分析法&#xff0c;以此实现缩…...

【安装笔记-20240613-Linux-在 OpenWrt 的 LuCI界面支持命令行调试】

安装笔记-系列文章目录 安装笔记-20240613-Linux-在 OpenWrt 的 LuCI界面支持命令行调试 文章目录 安装笔记-系列文章目录安装笔记-20240613-Linux-在 OpenWrt 的 LuCI界面支持命令行调试 前言一、软件介绍名称&#xff1a;ttyd主页官方介绍特点 二、安装步骤测试版本&#xf…...

React小记(一)_基础部分

1、项目搭建与结构 2、类组件和函数组件 主要区别&#xff1a;1、函数组件没有生命周期2、函数组件没有this指向3、函数组件没有状态4、函数组件通过hooks实现各种操作5、props在函数的第一个参数接收6、函数体相当于类组件的render函数import React from reactfunction App()…...

40、基于深度学习的线性预测设计(matlab)

1、原理及流程 深度学习的线性预测是一种利用深度神经网络模型进行线性回归预测的方法。其设计原理主要基于神经网络的层次化特性&#xff0c;利用多层感知器&#xff08;MLP&#xff09;等模型进行特征学习和非线性变换&#xff0c;从而提高线性预测的准确性。 设计流程如下…...

【初体验 threejs】【学习】【笔记】hello,正方体 3!

前言 为了满足工作需求&#xff0c;我已着手学习 Three.js&#xff0c;并决定详细记录这一学习过程。在此旅程中&#xff0c;如果出现理解偏差或有其他更佳的学习方法&#xff0c;请大家不吝赐教&#xff0c;在评论区给予指正或分享您的宝贵建议&#xff0c;我将不胜感激。 项…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...