归并排序模板
模板在文末,以下步骤方便理解记忆。
先贴一张快速排序模板步骤,用于对比记忆

归并排序步骤:
(0)如果数组左边界L ≥ 数组右边界,则不需要排序,直接return。
(1)直接取数组正中间的数,即 mid = (L+R) / 2为边界。
(2)先递归,对 L~mid ,mid+1 ~ R 这两个区间的数组调用归并排序函数。
(3)对于每次归并,它的面前有两个排好序的数组,即 [ L, mid ] 和 [ mid+1, R ],接下来需要把这两个数组合为另一个有序的数组。
具体操作是采用双下标指针,首先令 i = L,j = mid + 1(即两个数组的左边界)
接着,让q[ i ]和q[ j ]中更小的那个先放进 temp 数组里,然后 i++ 或 j++,以此类推。
当其中一个下标指针到达末端时,直接将另一个数组原封不动的拷贝进 temp 数组里。
(4)最后把 temp 数组拷贝到 q 数组中。(这一步容易写错)

#include<iostream>
using namespace std;const int N = 100010;int n;
int q[N], temp[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) //对应步骤(3),而且当两个数组的指针都没有越界时才这么做{if(q[i] < q[j]) temp[k++] = q[i++];else temp[k++] = q[j++];}while(i <= mid) temp[k++] = q[i++]; //如果i没有越界,则将i后面的原封不动地拷贝进去while(j <= r) temp[k++] = q[j++]; //如果j没有越界,则将j后面拷贝进去//q和temp数组的范围不同,因此需要两个变量i,j// 注意不是i <= nfor(int i=l, j=0; i <= r; ++i, ++j) q[i] = temp[j]; //步骤(4),注意写法
}int main()
{scanf("%d", &n);for(int i=0;i<n;++i) scanf("%d", &q[i]);merge_sort(q, 0, n-1);for(int i=0;i<n;++i) printf("%d ", q[i]);return 0;
}
相关文章:
归并排序模板
模板在文末,以下步骤方便理解记忆。 先贴一张快速排序模板步骤,用于对比记忆 归并排序步骤: (0)如果数组左边界L ≥ 数组右边界,则不需要排序,直接return。 (1)直接取…...
【NVIDIA】Jetson Orin Nano系列:安装 Qt6、firefox、jtop、flameshot
1、使用命令安装 sudo apt install qtcreator sudo apt install qt6-* sudo apt install libqt6* sudo apt install qml-qt6 sudo apt install qmlscene-qt6 sudo apt install assistant-qt6 sudo apt install designer-qt62、启动 qtcreator 3、常用工具安装 sudo apt in…...
Fastapi+Jsonp实现前后端跨域请求
文章目录 一、实现方法1.后端部分【Fastapi】2.前端部分【JS】二、测试一、实现方法 1.后端部分【Fastapi】 # coding:utf-8import json from fastapi import FastAPI, Response from fastapi.middleware.cors import CORSMiddlewareapp = FastAPI(...
MacOS受欢迎的数据库开发工具 Navicat Premium 15 中文版
Navicat Premium 15 Mac是一款数据库管理工具,提供了一个全面的解决方案,用于连接、管理和维护各种数据库系统。以下是Navicat Premium 15 Mac的一些主要功能和特点: 软件下载:Navicat Premium 15 中文版下载 多平台支持ÿ…...
helm---自动化一键部署
什么是helm?? 在没有这个helm之前,deployment service ingress helm的作用就是通过打包的方式,把deployment service ingress 这些打包在一块,一键式部署服务,类似于yum 官方提供的一个类似于安装仓库的功能,可以实…...
求助帖(setiosflags)的左右对齐问题:
以后自己要注意,如果两个相互矛盾的标志同时被设置,如先设置 setiosflags(ios::right),然后又设置 setiosflags(ios::left),那么结果可能就是两个标志都不起作用。因此,在设置了某标志,又要设置其他与之矛盾…...
升级8.0:民生手机银行的“内容解法”
数字化浪潮,滚滚来袭。 随着数字中国建设的持续推进,数字经济正在蓬勃发展。中商产业研究院分析师预测,2023年中国数字经济市场规模将增长至56.7万亿元,占GDP的比重将达到43.5%。 在此浪潮下,数字化的触角蔓延到各行…...
Kubernetes多租户实践
由于namespace本身的限制,Kubernetes对多租户的支持面临很多困难,本文梳理了K8S多租户支持的难点以及可能的解决方案。原文: Multi-tenancy in Kubernetes 是否应该让多个团队使用同一个Kubernetes集群? 是否能让不受信任的用户安全的运行不受信任的工作…...
【GEE】GEE反演地表温度相关问题说明(空洞、Landsat9数据集等)
之前分享了基于GEE-Landsat8数据集地表温度反演(LST热度计算),最近有很多小伙伴私信我很多问题,一一回复太慢了,所以今天写篇文章统一回答一下大家的问题。 问题1:数据有很多空洞、某些条带没有数据等 问题…...
【蓝桥备赛】数组分割——组合数学?
题目链接 数组分割 个人思路 两个数组都需要和为偶数,那么就去思考一个数组如何才能和是偶数呢?? 数组里肯定要么是奇数要么是偶数,偶数无论有多少个,都不会改变一个数组的奇偶性。但是奇数个奇数的和还是奇数&…...
iphone5s基带部分电源部分主主电源供电及
时序: 1.,基带电源的供电,基带电源也叫pmu。 首先时序图说电池提供供电,电池是J6接口,视频习惯把接口称之为座子。查U2_RF芯片,发现供电信号为PP_BATT_VCC_CONN,但是没查到跟电池座子有关系,电池座子写的是…...
【每日一题】按分隔符拆分字符串
文章目录 Tag题目来源解题思路方法一:遍历方法二:getline 写在最后 Tag 【遍历】【getline】【字符串】【2024-01-20】 题目来源 2788. 按分隔符拆分字符串 解题思路 方法一:遍历 思路 分隔符在字符串开始和结束位置时不需要处理。 分隔…...
spawn_group_template | spawn_group | linked_respawn
字段介绍 spawn_group | spawn_group_template 用来记录与脚本事件或boss战斗有关的 creatures | gameobjects 的刷新数据linked_respawn 用来将 creatures | gameobjects 和 boss 联系起来,这样如果你杀死boss, creatures | gameobjects 在副本重置之前…...
软考系分之计算机网络规划设计、综合布线、RAID和网络存储等
文章目录 1、概要2、网络的三层模型3、综合布线系统4、廉价磁盘冗余阵列(RAID)5、网络存储6、总结 1、概要 本篇重点介绍计算机网络中的网络规划设计、综合布线、RAID和网络存储。 2、网络的三层模型 三层模型分为核心层、汇聚层和接入层,接…...
使用ElEment组件实现vue表单校验空值
1.绑定表单组件数组rules 2.在data域中设定组件rules 3.设定调用方法函数 提交校验 取消: 测试页面 提交空值 失去焦点 取消重置 提交后重置...
processing集训day01
介绍 Processing是一门开源编程语言,提供了对图片,动画和声音进行编程的环境。学生,艺术家,设计师,建筑师,研究人员和业余爱好者可以使用Processing进行学习,制作原型以及作为生产工具。你可以…...
java面试——juc篇
目录 一、线程基础 1、进程与线程的区别?(⭐⭐⭐) 2、并行和并发的区别(⭐) 3、创建线程的方式有哪些?(⭐⭐⭐⭐) runnable和Callable的区别: 线程中的run()和 star…...
CSS 实现卡片以及鼠标移入特效
CSS 实现卡片以及鼠标移入特效 文章目录 CSS 实现卡片以及鼠标移入特效0、效果预览默认鼠标移入后 1、创建卡片组件2、添加样式3、完整代码 0、效果预览 默认 鼠标移入后 在本篇博客中,我们将探讨如何使用 CSS 来实现卡片组件,并添加鼠标移入特效&#…...
芯课堂 | SWM34S系列驱动TFT-LCD显示模组应用基本注意事项
1、确认硬件的连接、包括电源、地、RGB 数据线、DCLK\DE\HSYNC\VSYNC 等,显示模组有 DISP、RESET、CS、SCL、SDA 等。 2、确认各电压的正常,包括电源,部分有 IOVCC、VGL、VGH、VCOM 等电压 3、如果应用的 TFT-LCD 模组非演示例程中已适配调…...
java8 列表通过 stream流 根据对象属性去重的三种实现方法
java8 列表通过 stream流 根据对象属性去重的三种实现方法 一、简单去重 public class DistinctTest {/*** 没有重写 equals 方法*/SetterGetterToStringAllArgsConstructorNoArgsConstructorpublic static class User {private String name;private Integer age;}/*** lombo…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
