当前位置: 首页 > 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;我将不胜感激。 项…...

第04章:IDEA的安装与使用

第04章&#xff1a;随堂复习与企业真题&#xff08;IDEA安装与使用&#xff09; 一、随堂复习 1. IDEA的认识 IDEA(集成功能强大、符合人体工程学&#xff08;设置人性化&#xff09;)Eclipse 2. IDEA的下载、安装、卸载 卸载&#xff1a;使用控制面板进行卸载&#xff0c;…...

[原创][Delphi多线程]使用TMonitor, TEvent和TQueue配合实现TThreadQueue的经典使用案例.

[简介] 常用网名: 猪头三 出生日期: 1981.XX.XX QQ: 643439947 个人网站: 80x86汇编小站 https://www.x86asm.org 编程生涯: 2001年~至今[共22年] 职业生涯: 20年 开发语言: C/C、80x86ASM、PHP、Perl、Objective-C、Object Pascal、C#、Python 开发工具: Visual Studio、Delph…...

6.12ctf练习

[西湖论剑 2022]Node Magical Login 源码在这里&#xff1a;GitHub - CTF-Archives/2022-xhlj-web-node_magical_login: A web challenge in 2022 西湖论剑大赛打开 打开环境是个登录框&#xff0c;先进行了扫描和抓包都没有看见什么有价值的东西&#xff0c;看源码 大致连接…...

海豚调度异常处理: 使用 arthas 在内存中删除启动失败的工作流

&#x1f4a1; 本系列文章是 DolphinScheduler 由浅入深的教程&#xff0c;涵盖搭建、二开迭代、核心原理解读、运维和管理等一系列内容。适用于想对 DolphinScheduler了解或想要加深理解的读者。祝开卷有益。大数据学习指南 大家好&#xff0c;我是小陶&#xff0c;DolphinSch…...

在Qt中,QSerialPort::write(data) 和 readAll() 有什么关联和联系

在Qt中&#xff0c;QSerialPort::write(data) 和 readAll() 是与串行通信相关的两个不同的函数&#xff0c;它们属于 QSerialPort 类。这两个函数在串行通信中扮演不同的角色&#xff0c;但它们之间存在一定的联系&#xff1a; QSerialPort::write(data) 这个函数用于将数据发…...

第 2 章:Spring Framework 中的 IoC 容器

控制反转&#xff08;Inversion of Control&#xff0c;IoC&#xff09;与 面向切面编程&#xff08;Aspect Oriented Programming&#xff0c;AOP&#xff09;是 Spring Framework 中最重要的两个概念&#xff0c;本章会着重介绍前者&#xff0c;内容包括 IoC 容器以及容器中 …...

构造函数、实例、原型对象三者之间的关系

在 JavaScript 中&#xff0c;构造函数、实例和原型对象之间有着密切的关系。下面是对它们之间关系的详细解析和代码示例&#xff1a; 构造函数&#xff1a;构造函数是一个特殊的函数&#xff0c;用于创建对象的模板。它定义了对象的属性和方法。构造函数通常以大写字母开头&a…...

人工智能抢走了他们的工作。现在他们得到报酬,让它听起来像人类

人工智能抢走了他们的工作。现在他们得到报酬&#xff0c;让它听起来像人类 如果你担心人工智能会如何影响你的工作&#xff0c;那么广告文案的世界或许能让你窥见未来。 作家本杰明米勒(化名)在2023年初非常红火。他领导了一个由60多名作家和编辑组成的团队&#xff0c;发表博…...

大模型微调出错的解决方案(持续更新)

大家好,我是herosunly。985院校硕士毕业,现担任算法研究员一职,热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算法…...

企业多云策略的优势与实施指南

企业在选择云服务提供商时&#xff0c;常见的选项包括亚马逊AWS、微软Azure、谷歌云GCP、阿里云、腾讯云和华为云。为了避免过度依赖单一供应商&#xff0c;许多企业选择采用多云策略&#xff0c;这样可以充分利用不同云服务的优势&#xff0c;同时避免重复工作和其他额外的工作…...

企业信息管理系统案例/seo外包服务方案

【www.ahanw.cn--心得体会】随着信息技术的不断发展&#xff0c;多媒体教学成为活跃课堂、调动学生学习积极性的一种主要手段。下面是小编整理的相关内容&#xff0c;希望对你有帮助。信息化教学心得体会一在学校信息化建设和应用发展这样一个新背景下&#xff0c;作为学校领导…...

如何提高网站的点击量/百度网盘提取码入口

CRF(conditional random field algorithm) 求解用到的知识点是 viterbi lr( logistics regression) 1、基本公式 和是特征函数&#xff0c;转移特征函数&#xff0c;状态特征函数&#xff0c;和是对应的权值&#xff0c;是规范因子&#xff0c;求和是在所有可能的输出序列上进…...

平顶山城市住房城乡建筑网站/seo系统培训课程

2019独角兽企业重金招聘Python工程师标准>>> 1、什么是plist文件&#xff1f; 在做iOS开发时&#xff0c;我们应该经常会用到plist文件&#xff0c;那么什么是plist文件呢&#xff1f;它全名是Property List&#xff0c;属性列表文件&#xff0c;它是一种用来存储串…...

网站怎么做图片按按钮跳转/百度搜索引擎提交入口

晚上的时候PC问了一下这玩意&#xff0c;回忆一下极角排序 相关链接&#xff1a; How Many Triangles HDU - 5784&#xff08;极角排序&#xff0c;双指针&#xff09; 2019秦皇岛A - Angle Beats Gym - 102361A&#xff08;极角排序&#xff0c;多少个直角三角形&#xff09;…...

广州网站建设第一公司/小说关键词提取软件

摘要&#xff1a;从零开始写爬虫&#xff0c;初学者的速成指南&#xff01; 本期我们来聊聊URL去重那些事儿。以前我们曾使用Python的字典来保存抓取过的URL&#xff0c;目的是将重复抓取的URL去除&#xff0c;避免多次抓取同一网页。爬虫会将待抓取的URL放在todo队列中&#x…...

贵阳企业做网站/百度关键词工具入口

背景 最近想让Flutter 项目运行到浏览器试一下&#xff0c;按照一些博客说明&#xff0c;做了下面的操作。 flutter config --enable-web // 打开web配置 flutter run -d chrome //运行到chrome报错找不到chrome&#xff0c;执行flutter devices 也找不到浏览器&#xff0c;文…...