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

AcWing 787. 归并排序——算法基础课题解

AcWing 787. 归并排序

文章目录

        • 题目描述
        • C++
        • Go
        • 模板

题目描述

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤100000

输入样例

5
3 1 2 4 5

输出样例

1 2 3 4 5
C++
#include <iostream>using namespace std;const int N = 1e5 + 10;int tmp[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 k = 0, i = l, j = mid + 1;while (i <= mid && j <= r) {if (q[i] <= q[j]) tmp[k++] = q[i++];else tmp[k++] = q[j++];}while (i <= mid) tmp[k++] = q[i++];while (j <= r) tmp[k++] = q[j++];for (i = l; i <= r; i++) q[i] = tmp[i - l];
}int main() {int n;cin >> n;int q[N];for (int i = 0; i < n; i++) cin >> q[i];merge_sort(q, 0, n - 1);for (int i = 0; i < n; i++) cout << q[i] << " ";return 0;
}
Go
package mainimport "fmt"const N = 1e5 + 10var tmp = make([]int, N)func mergeSort(arr []int, l, r int) {if l >= r {return}mid := (l + r) >> 1mergeSort(arr, l, mid)mergeSort(arr, mid+1, r)k := 0i := lj := mid + 1for i <= mid && j <= r {if arr[i] <= arr[j] {tmp[k] = arr[i]i++} else {tmp[k] = arr[j]j++}k++}for i <= mid {tmp[k] = arr[i]i++k++}for j <= r {tmp[k] = arr[j]j++k++}for i := l; i <= r; i++ {arr[i] = tmp[i-l]}
}func main() {var n intfmt.Scanf("%d", &n)arr := make([]int, N)for i := 0; i < n; i++ {fmt.Scanf("%d", &arr[i])}mergeSort(arr, 0, n-1)for i := 0; i < n; i++ {fmt.Printf("%d ", arr[i])}
}
模板
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 k = 0, i = l, j = mid + 1;while (i <= mid && j <= r)if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];else tmp[k ++ ] = q[j ++ ];while (i <= mid) tmp[k ++ ] = q[i ++ ];while (j <= r) tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

相关文章:

AcWing 787. 归并排序——算法基础课题解

AcWing 787. 归并排序 文章目录 题目描述CGo模板 题目描述 给定你一个长度为 n 的整数数列。 请你使用归并排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行&#xff0c;第一行包含整数 n。 第二行包含 n 个整数&#xff08;所有…...

力扣1379---找出克隆二叉树的相同节点(Java、DFS、简单题)

目录 题目描述&#xff1a; 思路描述&#xff1a; 代码&#xff1a; &#xff08;1&#xff09;&#xff1a; &#xff08;2&#xff09;&#xff1a; 题目描述&#xff1a; 给你两棵二叉树&#xff0c;原始树 original 和克隆树 cloned&#xff0c;以及一个位于原始树 ori…...

FLink学习(三)-DataStream

一、DataStream 1&#xff0c;支持序列化的类型有 基本类型&#xff0c;即 String、Long、Integer、Boolean、Array复合类型&#xff1a;Tuples、POJOs 和 Scala case classes Tuples Flink 自带有 Tuple0 到 Tuple25 类型 Tuple2<String, Integer> person Tuple2.…...

Failed to resolve import “Home/components/HomeNew.vue“. Does the file exist?

错误信息 [plugin:vite:import-analysis] Failed to resolve import "/apis/home.js" from "src/views/Home/components/HomeNew.vue". Does the file exist? 错误原因 路径错误 解决方法...

《价值》-张磊-高瓴资本-3-建立人脉和信任;顺应趋势,把握机遇;

第三章 价值投资初试炼 2005.6.1 创办高瓴资本 许多人问我为什么一直在创业&#xff0c;其实我倒没想到自己非要创业成功不可&#xff0c;只是觉得一定要做点事&#xff0c;做点有意义的事。归根到底&#xff0c;可能是“爱折腾&#xff0c;不满足现状&#xff0c;爱挑战自己”…...

游戏引擎中的物理应用

一、 角色控制器 Character Controller和普通的动态对象&#xff08;Dynamic Actor &#xff09;是不同的&#xff0c;主要的三个特点是: 它拥有可控制的刚体间的交互假设它是有无穷的摩擦力&#xff08;可以站停在位置上&#xff09;&#xff0c;没有弹性加速和刹车几乎立即…...

复现k8s黄金票据学习

1.什么是黄金票据 在 Kubernetes 中&#xff0c;"黄金票据"并不是一个常见的术语。可能你想了解的是服务账户&#xff08;Service Account&#xff09;。服务账户是 Kubernetes 中用于身份验证和授权的一种机制。它们允许 Pods 或其他工作负载在 Kubernetes 集群中与…...

08-JavaScript BOM定时器及JS动画

1. 设置定时器 1.1设置超时定时器 超时调用需要使用window对象的setTimeout()方法&#xff0c;该方法接受两个参数&#xff1a;调用函数或计算表达式和以毫秒为单位的时间&#xff08;即在执行代码前需要等待多少毫秒&#xff09;。 //setTimeout(callback, after) //callba…...

边缘计算盒子与云计算:谁更适合您的业务需求?

边缘计算盒子和云计算&#xff0c;这两个概念听起来可能有点复杂&#xff0c;但其实它们就是两种不同的数据处理方式。那谁更适合您的业务需求呢&#xff1f;咱们来详细说说。 边缘计算盒子&#xff0c;就像是个小型的数据处理中心&#xff0c;放在离你业务现场比较近的地方。它…...

浅聊什么是Redis?

需求&#xff1a;MySQL面临大量的查询&#xff0c;即读写操作&#xff0c;因此类比CPU&#xff0c;给数据加缓存&#xff0c;Redis诞生。应用程序从MySQL查询的数据&#xff0c;在Redis设置缓存&#xff08;记录在内存中&#xff0c;无需IO操作&#xff09;&#xff0c;后再需要…...

java算法day43 | ● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

1049. 最后一块石头的重量 II 核心思想&#xff1a; 尽量让石头分成重量相同的两堆&#xff0c;相撞之后剩下的石头最小&#xff0c;这样就化解成01背包问题了。 是不是感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。那么分成两堆石头&#xff0c;一堆石头的…...

练气第六天

问:ANR怎么分析&#xff1f; ANR问题&#xff0c;这其实是一个非常综合性的问题&#xff0c;因为anr会涉及CPU负载&#xff0c;内存空间大小&#xff0c;线程锁&#xff0c;GC回收&#xff0c;这里面每个点&#xff0c;都是非常考验我们基本功的。 分析ANR问题&#xff0c;需…...

认识 Redis 与 分布式

Redis 官网页面 Redis官网链接 Redis 的简介 Redis 是一个在内存中存储数据的中间件 一方面用于作为数据库&#xff0c;另一方面用于作为数据缓存&#xff0c;适用于分布式系统中 Redis 基于网络&#xff0c;进行进程间通信&#xff0c;把自己内存中的变量给别的进程&#xf…...

Linux初学(十二)AWK进阶

一、AWK 1.1 简介 AWK是Linux中重要的文本处理工具Linux三剑客只一处理的对象可以是一个具体的文件&#xff0c;也可以是一个命令的执行结果AWK按行读取文件&#xff0c;将每一行视为一条记录 案例一&#xff1a;获取系统中每个用户的uid 方法一&#xff1a;cat /etc/passwd |…...

文字识别 Optical Character Recognition,OCR CTC STN

文字识别 Optical Character Recognition,OCR 自然场景文本检测识别技术综述 将图片上的文字内容,智能识别成为可编辑的文本。 场景文字识别(Scene Text Recognition,STR) OCR(Optical Character Recognition, 光学字符识别)传统上指对输入扫描文档图像进行分析处理,识…...

四、MySQL读写分离之MyCAT

一、读写分离概述 1、什么是读写分离&#xff1a; 读写分离&#xff1a;就是将读写操作分发到不同的服务器&#xff0c;读操作分发到对应的服务器 &#xff08;slave&#xff09;&#xff0c;写操作分发到对应的服务器&#xff08;master&#xff09; ① M-S (主从) 架构下&…...

通讯录项目实现

引言&#xff1a;通过顺序表的逻辑实现通讯录。这里就不讲关于顺序表的函数了。如果有不明白的可以看我写的顺序表的博客。 目录 顺序表与通讯录的比较 各源文件文件大榄 Contact.c中通讯录相关函数的定义 初始化和销毁通讯录 添加联系人&#xff1a; 删除联系人&#xf…...

xss相关知识点与绕过思路总结

前言 对xss的绕过进行了系统的学习与实践后&#xff0c;重新审视一下xss&#xff0c;对他的绕过进行一个总结。 &#xff08;当然我也是个小白&#xff0c;这些也是我当时瞎鸡儿乱搞绕过了几个xss自己做的小总结&#xff09; 可能有点丑陋&#xff0c;献丑了。 好博客推荐 …...

深入解析语言模型:原理、实战与评估

引言 随着人工智能的飞速发展&#xff0c;语言模型作为自然语言处理&#xff08;NLP&#xff09;的核心技术之一&#xff0c;日益受到业界的广泛关注。本文旨在深入探讨语言模型的原理、实战应用以及评估方法&#xff0c;帮助读者更好地理解和应用这一技术。 一、语言模型原理…...

Elasticsearch 的索引优化常规项

优化常规项 https://blog.csdn.net/bairo007/article/details/132019575 1、按实际情况适当调整主分片的数量 如果主分片数量太少&#xff0c;会导致每个分片中的数据量过大&#xff0c;而且无法利用集群中所有节点的计算资源。如果主分片数量太多&#xff0c;会导致索引过度…...

Element React:革新性UI组件库助力React开发者高效构建企业级应用界面

Element React&#xff1a;革新性UI组件库助力React开发者高效构建企业级应用界面 【免费下载链接】element-react Element UI 项目地址: https://gitcode.com/gh_mirrors/el/element-react 在现代Web应用开发中&#xff0c;界面构建往往占据了开发者大量时间与精力。El…...

终极指南:如何在Chainer中构建强大的循环神经网络(RNN)

终极指南&#xff1a;如何在Chainer中构建强大的循环神经网络(RNN) 【免费下载链接】chainer A flexible framework of neural networks for deep learning 项目地址: https://gitcode.com/gh_mirrors/ch/chainer 想要掌握深度学习中的序列建模吗&#xff1f;Chainer框架…...

APKMirror:安卓应用安全管理的终极解决方案

APKMirror&#xff1a;安卓应用安全管理的终极解决方案 【免费下载链接】APKMirror 项目地址: https://gitcode.com/gh_mirrors/ap/APKMirror 您是否曾在寻找安卓应用的特定版本时感到无从下手&#xff1f;是否担忧从第三方渠道下载的APK文件可能存在安全隐患&#xff…...

【20年ETL老兵亲授】Polars 2.0清洗Pipeline黄金架构:从schema-on-read校验→增量物化→自动fallback机制的闭环设计

第一章&#xff1a;Polars 2.0大规模数据清洗的范式演进与核心挑战Polars 2.0标志着声明式、惰性计算与零拷贝内存管理在数据清洗场景中的深度整合。相比传统Pandas的命令式逐行处理与隐式副本机制&#xff0c;Polars 2.0将整个清洗流水线建模为逻辑计划&#xff08;Logical Pl…...

故障诊断指南:用STFT在5分钟内定位工业设备异常时间点(MATLAB版)

故障诊断实战&#xff1a;STFT在工业设备异常定位中的高效应用&#xff08;MATLAB实现&#xff09; 工业设备的异常检测如同医生听诊&#xff0c;需要精准捕捉故障的"心跳节律"。传统方法往往只能告诉我们"设备病了"&#xff0c;却难以定位"何时发病…...

企业级工作流系统实战:30分钟从零搭建RuoYi-Flowable-Plus

企业级工作流系统实战&#xff1a;30分钟从零搭建RuoYi-Flowable-Plus 【免费下载链接】RuoYi-Flowable-Plus 本项目基于 RuoYi-Vue-Plus 进行二次开发扩展Flowable工作流功能&#xff0c;支持在线表单设计和丰富的工作流程设计能力。如果觉得这个项目不错&#xff0c;麻烦点个…...

新手入门实战:基于 Spring Boot 的计算机毕设题目推荐管理系统设计与实现

对于计算机专业的同学来说&#xff0c;毕业设计&#xff08;毕设&#xff09;是大学学习成果的一次重要检验。然而&#xff0c;选题环节往往令人头疼&#xff1a;题目来源分散、重复率高、与个人兴趣或能力不匹配&#xff0c;缺乏一个集中的平台进行管理和推荐。今天&#xff0…...

Dinky 1.2.3实战:手把手教你构建带多数据源Connector的Flink 1.20镜像并推上K8s

Dinky 1.2.3实战&#xff1a;构建多数据源Flink镜像与K8s集成全指南 1. 为什么需要定制Flink基础镜像&#xff1f; 在实时数据处理领域&#xff0c;Flink已成为事实上的标准计算引擎。但官方镜像往往只包含基础组件&#xff0c;当我们需要连接MySQL、Kafka、Paimon等不同数据源…...

革新性英雄联盟效率工具:League-Toolkit为玩家打造智能游戏体验

革新性英雄联盟效率工具&#xff1a;League-Toolkit为玩家打造智能游戏体验 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 在快节…...

开发者专属配置:OpenClaw+GLM-4-7-Flash优化命令行工作效率

开发者专属配置&#xff1a;OpenClawGLM-4-7-Flash优化命令行工作效率 1. 为什么开发者需要AI增强命令行&#xff1f; 作为每天与终端打交道的开发者&#xff0c;我经常遇到这样的困境&#xff1a;忘记复杂的grep参数组合、需要反复查阅历史命令、或是面对一长串docker compo…...