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

归并排序详解:递归实现+非递归实现(图文详解+代码)

文章目录

  • 归并排序
        • 1.递归实现
        • 2.非递归实现
        • 3.海量数据的排序问题


归并排序


  • 时间复杂度:O ( N * logzN ) 每一层都是N,有log2N层
  • 空间复杂度:O(N),每个区间都会申请内存,最后申请的数组大小和array大小相同
  • 稳定性:稳定

目前为止,稳定的排序有:插入、冒泡、归并

  • 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,采用了分治法

在这里插入图片描述

  • 将待排序列分解,先使每个子序列有序,再使子序列段间有序
  • 将已有序的子序列合并,得到完全有序的序列
  • 若将两个有序表合并成一个有序表,称为二路归并
1.递归实现

在这里插入图片描述

  • 1.确定递归的结束条件,求出中间数mid,
  • 2.进行分解,根据mid来确定递归的区间大小
  • 3.递归分解完左边,然后递归分解右边
  • 4.左右分解完成后,进行合并
  • 5.申请新数组进行合并,比较两个数组段,记得查漏补缺
  • 6.和并的时候要对齐下标,每个tmp的下标要找到array中对应的下标
/*** 归并排序* @param array*/public static void mergeSort(int[] array) {mergeSortFunc(array,0,array.length-1);}private static void mergeSortFunc(int[] array, int left, int right) {//结束条件if (left >= right) {return;}//进行分解int mid = (left + right) / 2;mergeSortFunc(array, left, mid);mergeSortFunc(array, mid + 1, right);//左右分解完成后,进行合并merge(array, left, right, mid);}//进行合并private static void merge(int[] array, int start, int end, int mid) {int s1 = start;int s2 = mid + 1;int[] tmp = new int[end - start + 1];int k = 0;//k为tmp数组的下标while (s1 <= mid && s2 <= end) {//两个数组中都有数据//进行比较,放到新申请的数组if (array[s1] <= array[s2]) {tmp[k++] = array[s1++];} else {tmp[k++] = array[s2++];}}//因为有&&条件,数组不一定走完while (s1 <= mid) {tmp[k++] = array[s1++];}while (s2 <= end) {tmp[k++] = array[s2++];}//此时,将排好的tmp数组的数组,拷贝到arrayfor (int i = 0; i < tmp.length; i++) {array[i+start] = tmp[i];//对齐下标}}
2.非递归实现

在这里插入图片描述

  • 1.从1开始分组,先保证每个数都是独立有序的
  • 2.进行循环,i下标从0开始,每次跳转组数的两倍
  • 3.根据left = i,求出mid和right
  • 4.要避免mid和right越界
  • 5.分组进行合并
  • 6.二倍数扩大组数
/**** 归并排序,非递归实现* @param array*/public static void mergeSort2(int[] array) {int gap = 1;while (gap < array.length) {//i += gap * 2 i每次跳到下一组for (int i = 0; i < array.length; i += gap * 2) {int left = i;//要避免mid和right越界int mid = left + gap - 1;if(mid>=array.length){mid = array.length-1;//修正越界的情况}int right = mid + gap;if (right>=array.length){//修正越界的情况right = array.length-1;}merge(array,left,right,mid);//进行合并}gap *=2;//2倍数扩大组数}}//进行合并private static void merge(int[] array, int start, int end, int mid) {int s1 = start;int s2 = mid + 1;int[] tmp = new int[end - start + 1];int k = 0;//k为tmp数组的下标while (s1 <= mid && s2 <= end) {//两个数组中都有数据//进行比较,放到新申请的数组if (array[s1] <= array[s2]) {tmp[k++] = array[s1++];} else {tmp[k++] = array[s2++];}}//因为有&&条件,数组不一定走完while (s1 <= mid) {tmp[k++] = array[s1++];}while (s2 <= end) {tmp[k++] = array[s2++];}//此时,将排好的tmp数组的数组,拷贝到arrayfor (int i = 0; i < tmp.length; i++) {array[i + start] = tmp[i];//对齐下标}}
3.海量数据的排序问题

外部排序:排序过程需要在磁盘等外部存储进行的排序

前提:内存只有 1G,需要排序的数据有 100G

因为内存中因为无法把所有数据全部放下,所以需要外部排序,而归并排序是最常用的外部排序

  1. 先把文件切分成 200 份,每个 512 M
  2. 分别对 512 M 排序,因为内存已经可以放的下,所以任意排序方式都可以
  3. 进行 2路归并,同时对 200 份有序文件做归并过程,最终结果就有序了

点击移步博客主页,欢迎光临~

偷cyk的图

相关文章:

归并排序详解:递归实现+非递归实现(图文详解+代码)

文章目录 归并排序1.递归实现2.非递归实现3.海量数据的排序问题 归并排序 时间复杂度&#xff1a;O ( N * logzN ) 每一层都是N,有log2N层空间复杂度&#xff1a;O&#xff08;N&#xff09;&#xff0c;每个区间都会申请内存&#xff0c;最后申请的数组大小和array大小相同稳定…...

DataBinding原理

1、MainActivity首先使用DataBindingUtil.setContentView设置布局文件activity_main.xml。 2、随后&#xff0c;经过一系列函数调用&#xff0c;ActivityMainBindingImpl对象最终会实例化&#xff0c;并与activity_main.xml进行绑定。 3、实例化后的ActivityMainBindingImpl对象…...

docker更换国内源

docker更换国内源 1、编辑Docker配置文件 在终端中执行以下命令&#xff0c;编辑Docker配置文件&#xff1a; vi /etc/docker/daemon.json2、添加更新源 在打开的配置文件中&#xff0c;添加以下内容&#xff1a; {"registry-mirrors": ["https://hub-mirror…...

【咖啡品牌分析】Google Maps数据采集咖啡市场数据分析区域分析热度分布分析数据抓取瑞幸星巴克

引言 咖啡作为一种受欢迎的饮品&#xff0c;已经成为我们生活中不可或缺的一部分。随着国内外咖啡品牌的涌入&#xff0c;新加坡咖啡市场愈加多元化和竞争激烈。 本文对新加坡咖啡市场进行了全面的品牌门店数占比分析&#xff0c;聚焦于热门品牌的地理分布、投资价值等。通过…...

【Java】异常处理(一)

&#x1f33a;个人主页&#xff1a;Dawn黎明开始 &#x1f380;系列专栏&#xff1a;Java ⭐每日一句&#xff1a;什么都不做&#xff0c;才会来不及 &#x1f4e2;欢迎大家&#xff1a;关注&#x1f50d;点赞&#x1f44d;评论&#x1f4dd;收藏⭐️ 文章目录 &#x1f4cb;前…...

【高级程序设计】Week2-4Week3-1 JavaScript

一、Javascript 1. What is JS 定义A scripting language used for client-side web development.作用 an implementation of the ECMAScript standard defines the syntax/characteristics of the language and a basic set of commonly used objects such as Number, Date …...

PHP笔记-->读取JSON数据以及获取读取到的JSON里边的数据

由于我以前是写C#的&#xff0c;现在学一下PHP&#xff0c; 在读取json数据的时候被以前的思维卡住了。 以前用C#读取的时候&#xff0c;是先定义一个数组&#xff0c;将反序列化的json存到数组里面&#xff0c;在从数组里面获取jaon中的“data”数据。 其实PHP的思路也是一样…...

【Spring Boot】如何集成Redis

在pom.xml文件中导入spring data redis的maven坐标。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency> 在application.yml文件中加入redis相关配置。 spr…...

Elasticsearch备份与还原:使用elasticdump

在数据管理的世界里&#xff0c;备份和还原数据是重中之重的日常工作&#xff0c;特别是对于Elasticsearch这样的强大而复杂的搜索引擎。备份不仅可以用于灾难恢复&#xff0c;还可以在数据迁移、测试或者升级等场景中发挥重要作用。 在本博客中&#xff0c;我们将会重点介绍如…...

给大伙讲个笑话:阿里云服务器开了安全组防火墙还是无法访问到服务

铺垫&#xff1a; 某天我在阿里云上买了一个服务器&#xff0c;买完我就通过MobaXterm进行了ssh&#xff08;这个软件是会保存登录信息的&#xff09; 故事开始&#xff1a; 过了n天之后我想用这个服务器来部署流媒体服务&#xff0c;咔咔两下就部署好了流媒体服务器&#x…...

js:react使用zustand实现状态管理

文档 https://www.npmjs.com/package/zustandhttps://github.com/pmndrs/zustandhttps://docs.pmnd.rs/zustand/getting-started/introduction 安装 npm install zustand示例 定义store store/index.js import { create } from "zustand";export const useCount…...

vue3+vite+SQL.js 读取db3文件数据

前言&#xff1a;好久没写博客了&#xff0c;最近一直在忙&#xff0c;没时间梳理。最近遇到一个需求是读取本地SQLite文件&#xff0c;还是花费了点时间才实现&#xff0c;没怎么看到vite方面写这个的文章&#xff0c;现在分享出来完整流程。 1.pnpm下载SQL.js(什么都可以下)…...

微信小程序 限制字数文本域框组件封装

微信小程序 限制字数文本域框 介绍&#xff1a;展示类组件 导入 在app.json或index.json中引入组件 "usingComponents": {"text-field":"/pages/components/text-field/index"}代码使用 <text-field maxlength"500" bindtabsIt…...

阿里国际站(直通车)

1.国际站流量 2.直通车即P4P&#xff08;pay for performance点击付费&#xff09; 2.1直通的含义&#xff1a;按点击付费&#xff0c;通过自助设置多维度展示产品信息&#xff0c;获得大量曝光吸引潜在买家。 注意&#xff1a;中国大陆和尼日利尼地区点击不扣费。 2.2扣费规…...

C# GC机制

在C#中&#xff0c;垃圾回收&#xff08;Garbage Collection&#xff0c;简称GC&#xff09;是CLR&#xff08;公共语言运行时&#xff09;的一个重要部分&#xff0c;用于自动管理内存。它会自动释放不再使用的对象所占用的内存&#xff0c;避免内存泄漏&#xff0c;减少程序员…...

wpf devexpress在未束缚模式中生成Tree

TreeListControl 可以在未束缚模式中没有数据源时操作&#xff0c;这个教程示范如何在没有数据源时创建tree 在XAML生成tree 创建ProjectObject类实现数据对象显示在TreeListControl: public class ProjectObject {public string Name { get; set; }public string Executor {…...

Python利器:os与chardet读取多编码文件

在数据处理中会遇到读取位于不同位置的文件,每个文件所在的层级不同,而且每个文件的编码类型各不相同,那么如何高效地读取文件呢? 在读取文件时首先需要获取文件的位置信息,然后根据文件的编码类型来读取文件。本文将使用os获取文件路径,使用chardet得到文件编码类型。 …...

微服务和注册中心

微服务和注册中心是紧密相关的概念&#xff0c;可以说注册中心是微服务架构中必不可少的一部分。 在微服务架构中&#xff0c;系统被拆分成了若干个独立的服务&#xff0c;因此服务之间需要进行通信和协作。为了实现服务的发现和调用&#xff0c;需要一个中心化的注册中心来进…...

吴恩达《机器学习》9-1-9-3:反向传播算法、反向传播算法的直观理解

一、正向传播的基础 在正向传播中&#xff0c;从神经网络的输入层开始&#xff0c;通过一层一层的计算&#xff0c;最终得到输出层的预测结果。这是一种前向的计算过程&#xff0c;即从输入到输出的传播。 二、反向传播算法概述 反向传播算法是为了计算代价函数相对于模型参数…...

Java 算法篇-链表的经典算法:判断回文链表、判断环链表与寻找环入口节点(“龟兔赛跑“算法实现)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 链表的创建 2.0 判断回文链表说明 2.1 快慢指针方法 2.2 使用递归方式实现反转链表方法 2.3 实现判断回文链表 - 使用快慢指针与反转链表方法 3.0 判断环链表说明…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

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

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

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...