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

AcWing 787:归并排序

【题目来源】
https://www.acwing.com/problem/content/789/

【题目描述】
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

【输入格式】
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在 1∼10^9 范围内),表示整个数列。

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

【数据范围】
1≤n≤100000

【输入样例】
5
3 1 2 4 5

【输出样例】
1 2 3 4 5

【算法分析】
● 归并排序是一种常用且高效的排序算法,它采用分治法的思想来对序列进行排序。归并排序的基本思想是将序列分成较小的子序列,递归地对这些子序列进行排序,然后将它们合并在一起,产生最终的有序序列。归并排序模拟示意图如下所示。

● 归并排序采用分治法的思想来对序列进行排序,它的 mid 值是取待排序列的中间位置的元素序号作为基准值。归快速排序算法 https://blog.csdn.net/hnjzsyjyj/article/details/132669946 虽然也是采用分治法的思想来对序列进行排序,但是它的 mid 值是取待排序列的中间位置的元素值作为基准值。

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+5;
int a[maxn], tmp[maxn];void merge_sort(int v[],int le,int ri) {if(le>=ri) return;int mid=le+ri>>1;merge_sort(v,le,mid);merge_sort(v,mid+1,ri);int k=0;int i=le,j=mid+1;while(i<=mid && j<=ri) {if(v[i]<=v[j]) tmp[k++]=v[i++];else tmp[k++]=v[j++];}while(i<=mid) tmp[k++]=v[i++];while(j<=ri) tmp[k++]=v[j++];k=0;for(int i=le; i<=ri; i++) {a[i]=tmp[k++];}
}int main() {int n;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;
}/*
in:
5
3 1 2 4 5out:
1 2 3 4 5
*/





【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/119760879
https://blog.csdn.net/hnjzsyjyj/article/details/119787188
https://blog.csdn.net/hnjzsyjyj/article/details/119768122

https://www.acwing.com/solution/content/27445/





 

相关文章:

AcWing 787:归并排序

【题目来源】https://www.acwing.com/problem/content/789/【题目描述】 给定你一个长度为 n 的整数数列。 请你使用归并排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。【输入格式】 输入共两行&#xff0c;第一行包含整数 n。 第二行包含 n 个整数&#…...

SeamlessM4T—Massively Multilingual Multimodal Machine Translation

本文是LLM系列的文章&#xff0c;针对《SeamlessM4T—Massively Multilingual & Multimodal Machine Translation》的翻译。 SeamlessM4T&#xff1a;大规模语言多模态机器翻译 摘要1 引言2 多模态翻译的社会技术维度2.12.22.3 3 SeamlessAlign&#xff1a;自动创建语音对…...

Python数据分析-Numpy

Numpy 个人笔记&#xff0c;仅供参考&#xff0c;谢谢 导入 import numpy import numpy as np from numpy import *Numpy数组对象 引入 # 让列表1 a [1,2,3,4],b [4,5,6,7] [x1 for x in a] # 实现ab a b > [1,2,3,4,5,6,7,8] [x y for (x,y) in zip(a,b)] -------…...

【真题解析】系统集成项目管理工程师 2023 年上半年真题卷(案例分析)

本文为系统集成项目管理工程师考试(软考) 2023 年上半年真题(全国卷),包含答案与详细解析。考试共分为两科,成绩均 ≥45 即可通过考试: 综合知识(选择题 75 道,75分)案例分析(问答题 4 道,75分)案例分析(问答题*4)试题一试题二试题三试题四案例分析(问答题*4) …...

【GAMES202】Real-Time Global Illumination(in 3D)—实时全局光照(3D空间)

一、SH for Glossy transport 1.Diffuse PRT回顾 上篇我们介绍了PRT&#xff0c;并以Diffuse的BRDF作为例子分析了预计算的部分&#xff0c;包括Lighting和Light transport&#xff0c;如上图所示。 包括我们还提到了SH&#xff0c;可以用SH的有限阶近似拟合球面函数&#xff…...

金蝶云星空二开,公有云执行SQL

功能背景&#xff1b; 金蝶公有云执行sql工具&#xff0c;因官方为云部署 用户无法连接数据库增删改查 天梯维护网页仅支持增删改操作 二开单据已支持根据sql动态生成单据体 与sql可视化界面操作一致 功能实现及场景&#xff1a; 1.可用于公有云执行sql类操作 2.私有云部署&am…...

JAVA String 二维的字符串数组 String[][]

String[][] 表示一个二维的字符串数组&#xff0c;也可以称为字符串矩阵。它是由多个一维的字符串数组组成的&#xff0c;每个一维数组都表示矩阵中的一行。 在 Java 中&#xff0c;可以使用如下方式声明和初始化一个二维字符串数组&#xff1a; String[][] matrix new Strin…...

【Unity3D赛车游戏优化篇】【九】Unity中如何让汽车丝滑漂移?

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;Uni…...

el-dialog设置高度、使用resetFields清除表单项无效问题

初学者容易踩坑的的el-dialog、el-form问题 1. el-dialog设置高度2. el-form中表单项对不齐3. 使用resetFields清除表单项无效 1. el-dialog设置高度 在el-dialog中里面添加一个div设置固定高度&#xff0c;或者限制最小的高度。 <el-dialogtitle"选择图标"v-mod…...

MySql切换到达梦数据库,各种问题解决记录

参考官方文档&#xff1a; https://eco.dameng.com/document/dm/zh-cn/sql-dev/practice-func.html 1. 关键字导致的报错&#xff1a;如ref,comment,top,domain等 Error -2007: 第 1 行, 第 117 列[ref]附近出现错误: 语法分析出错解决方案&#xff1a;修改关键字即可 2. 查…...

2023开学礼山东财经大学《乡村振兴战略下传统村落文化旅游设计》许少辉新财经图书馆

2023开学礼山东财经大学《乡村振兴战略下传统村落文化旅游设计》许少辉新财经图书馆...

vscode中使用eslint+prettier的配置

eslintprettiervscode自动保存用起来感觉非常爽快。 一般来说&#xff0c;安装eslintprettier插件&#xff0c;然后使用相关脚手架配套的eslintprettier&#xff0c;无法自动格式代码&#xff0c;每次都需要执行格式化命令。这里贴出保存自动格式化代码的setting.json。 // .…...

HTML 标签讲解

HTML 标签讲解 HTML 语言结构根元素元数据元素主体根元素大纲元素文本内容语义化内联文本图像与多媒体编辑标识table表格内容表单内容table表单 HTML 语言结构 Markup &#xff08;标记、标签&#xff09;用来容纳和描述内容 严格意义上&#xff0c;标签是指开始标签&#xf…...

ue5 小知识点 ue的world type,pie editor game

说明以该命令行模式启动游戏的前提下的两个问题&#xff1a; 1.WITH_EDITOR中的代码会被编译 2.由于没有在编辑器中(即没有打开虚幻编辑器)&#xff0c;所以GIsEditor为false WITH_EDITOR和WITH_EDITORONLY_DATA的区别 在论坛中找到的答案&#xff1a; WITH_EDITORONLY_DAT…...

两表union 如何保证group by 字段唯一

当要计算的指标可能来源多个表时&#xff0c;可能会使用到union all把不同的表中计算的指标合起来。关于union all使用条件&#xff1a;两个要联合的SQL语句 字段个数必须一样&#xff0c;而且字段类型要“相容”&#xff08;一致&#xff09; 另外&#xff0c;回顾union和uni…...

【⑰MySQL】 变量 | 循环 | 游标 | 处理程序

前言 ✨欢迎来到小K的MySQL专栏&#xff0c;本节将为大家带来MySQL变量 | 循环 | 游标 | 处理程序的分享✨ 目录 前言1. 变量1.1系统变量1.2 用户变量 2. 定义条件与处理程序2.1 案例分析2.2 定义条件2.3 定义处理程序2.4 案例解决 3. 流程控制3.1 分支结构3.2 循环结构3.3 跳转…...

如何在arXiv上发表一篇文章

目录 1. 初始信息确认2. 提交论文文件3. 论文编译结果4. 补充论文信息5. 总览 1. 初始信息确认 版权问题需要根据个人情况选择。 IEEE, Elsevier, BioMed Central, 这几个出版商都允许在投稿之前挂文章到arXiv下。通常是选择&#xff1a; arXiv.org perpetual, non-exclusive l…...

重要性采样

重要性采样 前言 离散型随机变量 X X X&#xff0c;我们可以通过以下方法求取其期望&#xff1a; 直接计算法&#xff0c;需要知道概率分布&#xff1a; E ( X ) ∑ x ∈ X [ p ( x ) ⋅ x ] \mathbb{E}(X)\sum_{x\in X}\left[p(x)\cdot x\right] E(X)x∈X∑​[p(x)⋅x] 采…...

说说Omega架构

分析&回答 Omega架构我们暂且称之为混合数仓。 什么是ECS设计模式 在谈我们的解法的时候&#xff0c;必须要先提ECS的设计模式。 简单的说&#xff0c;Entity、Component、System分别代表了三类模型。 实体(Entity)&#xff1a;实体是一个普通的对象。通常&#xff0c…...

高忆管理:光刻胶概念强势拉升,同益股份、格林达涨停

光刻胶概念5日盘中强势拉升&#xff0c;截至发稿&#xff0c;同益股份、格林达涨停&#xff0c;波长光电、晶瑞电材涨超7%&#xff0c;容大感光涨逾5%&#xff0c;华懋科技、茂莱光学、苏大维格、南大光电等均走强。 音讯面上&#xff0c;据新加坡《联合早报》网站9月2日报导&…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

raid存储技术

1. 存储技术概念 数据存储架构是对数据存储方式、存储设备及相关组件的组织和规划&#xff0c;涵盖存储系统的布局、数据存储策略等&#xff0c;它明确数据如何存储、管理与访问&#xff0c;为数据的安全、高效使用提供支撑。 由计算机中一组存储设备、控制部件和管理信息调度的…...

react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架

1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...

统计学(第8版)——统计抽样学习笔记(考试用)

一、统计抽样的核心内容与问题 研究内容 从总体中科学抽取样本的方法利用样本数据推断总体特征&#xff08;均值、比率、总量&#xff09;控制抽样误差与非抽样误差 解决的核心问题 在成本约束下&#xff0c;用少量样本准确推断总体特征量化估计结果的可靠性&#xff08;置…...

自定义线程池1.2

自定义线程池 1.2 1. 简介 上次我们实现了 1.1 版本&#xff0c;将线程池中的线程数量交给使用者决定&#xff0c;并且将线程的创建延迟到任务提交的时候&#xff0c;在本文中我们将对这个版本进行如下的优化&#xff1a; 在新建线程时交给线程一个任务。让线程在某种情况下…...

【AI News | 20250609】每日AI进展

AI Repos 1、OpenHands-Versa OpenHands-Versa 是一个通用型 AI 智能体&#xff0c;通过结合代码编辑与执行、网络搜索、多模态网络浏览和文件访问等通用工具&#xff0c;在软件工程、网络导航和工作流自动化等多个领域展现出卓越性能。它在 SWE-Bench Multimodal、GAIA 和 Th…...

Qt 按钮类控件(Push Button 与 Radio Button)(1)

文章目录 Push Button前提概要API接口给按钮添加图标给按钮添加快捷键 Radio ButtonAPI接口性别选择 Push Button&#xff08;鼠标点击不放连续移动快捷键&#xff09; Radio Button Push Button 前提概要 1. 之前文章中所提到的各种跟QWidget有关的各种属性/函数/方法&#…...