当前位置: 首页 > 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日报导&…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...

Axure零基础跟我学:展开与收回

亲爱的小伙伴,如有帮助请订阅专栏!跟着老师每课一练,系统学习Axure交互设计课程! Axure产品经理精品视频课https://edu.csdn.net/course/detail/40420 课程主题:Axure菜单展开与收回 课程视频:...