漫画:什么是归并排序算法?

归并排序是建立在归并操作的一种高效的排序方法,该方法采用了分治的思想,比较适用于处理较大规模的数据,但比较耗内存,今天我们聊聊归并排序

一、排序思想

一天,小一尘和慧能坐在石头上,眺望着远方

image-20230212223830927

image-20230212223846275

image-20230212223859988

image-20210425154735224

image-20230212223930424

image-20230212223943221

分而治之: 分开来去治理

image-20230212223959308

image-20230212224011999

image-20230212224027406

归并即合并之意

慧能随手画了一张图解释了一下

image-20230212224048367

治:治理,这里就是将数组排序

image-20230212224101284

image-20230212224127250

image-20230212224143819

对于合并,其实非常简单,我只要不断地取出两个有序数组中比较小的那一个放在一个辅助数组中(通过比较),直到把两个有序数组中的元素取完

image-20230212224158909

image-20230212224219964

二、代码

image-20230212224239292

image-20230212224255908

一尘已经了解了师傅的固定套路了

既然是不断地分,那用递归就非常简单了,什么时候终止递归呢?递归到只有一个元素的时候。一尘随手写下了如下代码

image-20230212225129976

这里需要说明的是,center = (left + right) / 2 最好改成 center = left + (right - left) / 2,因为 left + right 有可能溢出。

很快,一尘写下了 merge 函数的代码

image-20230212225157452

image-20230212225217123

三、时间复杂度

image-20230212225306699

一尘想到:这个有点烧脑啊,元素个数为 n,运行时间是多少啊?递归,递归,再递归…

image-20230212225329890

师傅一下看出了一尘的心思

image-20230212225357296

image-20230212225412612

假设处理的数据规模大小为 N

运行时间设为:T(N)

① 当把 N 分为两半时,那么处理大小为 N/2 子数组花费时间为:T(N/2)

② 合并花费时间与数据规模成正比:N

所以处理规模大小为N的数据所需要花费两个大小为 N/2 的子数组加上合并花费的时间

即:T(N) = 2T(N/2) + N

对于 N = 1,T(1) = 1

image-20230212225638608

image-20230212225651102

image-20230212225711161

image-20230212225727920

image-20230212225743067

image-20230212225758088

四、稳定性

image-20230212225950515

image-20230212230011647

image-20230212230040545

此时太阳已经下山,一尘和师傅走在回家的路上,在路上,一尘脑子又想了一下归并排序的全过程

image-20230212230158300

更多排序算法文章

1. 漫画:什么是冒泡排序算法?

2. 漫画:什么是选择排序算法?

3. 漫画:什么是插入排序算法?

4. 漫画:什么是希尔排序算法?

5. 漫画:什么是归并排序算法?

6. 漫画:什么是快速排序算法?

7. 漫画:什么是堆排序算法?

8. 漫画:什么是基数排序算法?

9. 漫画:什么是外部排序?

10. 什么是计数排序?

11. 十大排序算法极简汇总篇

推荐阅读

下载破 2w+,在校生必看,《程序员内功修炼》第二版出炉

从双非到大厂,帅地写了一本原创PDF送给大家

一个帮你拿offer的校招网站

算法刷题路线(系统+全面)

作者简介:我是帅地,校招拿到过不少大厂offer,毕业去了腾讯研发岗,毕业半年整到人生第一个 100 万,目前专注于写大学规划 + 校招求职相关的内容,著有个人原创网站 PlayOffer。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Qt5.12实战之QByteArray与字符指针及字符串转换

示例源码:#include <QCoreApplication> #include <QDebug> #include <QTextStream> static QTextStream cout (stdout,QIODevice::WriteOnly); #include <iostream> #include <QtGlobal> #include <QByteArray>void test() {qDebug() <…

进程调度的基本过程

这里写目录标题什么是进程进程管理结构体或类的主要属性pid内存指针文件描述符表辅助进程调度的属性并发并行并发什么是进程 进程是操作系统对一个正在运行的程序的一种抽象&#xff0c;也就是说&#xff0c;一个运行起来的程序就是一个进程。 进程又是操作系统进行资源分配的…

百度终于要出手了?文心一言

文心一言 百度全新一代知识增强大语言模型&#xff0c;文心大模型家族的新成员&#xff0c;能够与人对话互动&#xff0c;回答问题&#xff0c;协助创作&#xff0c;高效便捷地帮助人们获取信息、知识和灵感。 前几天炒的风风火火的ChatGPT&#xff0c;虽然 ChatGPT 很强大&a…

【Error: ImagePullBackOff】Kubernetes中Nginx服务启动失败排查流程

❌pod节点启动失败&#xff0c;nginx服务无法正常访问&#xff0c;服务状态显示为ImagePullBackOff。 [rootm1 ~]# kubectl get pods NAME READY STATUS RESTARTS AGE nginx-f89759699-cgjgp 0/1 ImagePullBackOff 0 103…

【数据结构与算法】顺序表和链表

[数据结构与算法]顺序表和链表线性表线性表定义&#xff1a;顺序表静态顺序表动态顺序表动态顺序表的接口实现链表链表的概念链表的分类单向链表的接口实现双向链表循环的接口实现顺序表和链表的区别缓存利用率参考存储体系结构以及局部原理性存储体系结构Cache采用的程序访问的…

面试官问 : ArrayList 不是线程安全的,为什么 ?(看完这篇,以后反问面试官)

前言 金三银四 &#xff1f; 也许&#xff0c;但是。 近日&#xff0c;又收到金三银四一线作战小队成员反馈的战况 &#xff1a; 我不管你从哪里看的面经&#xff0c;但是我不允许你看到我这篇文章之后&#xff0c;还不清楚这个面试问题。 本篇内容预告&#xff1a; Array…

【基础算法】单链表的OJ练习(5) # 环形链表 # 环形链表II # 对环形链表II的解法给出证明(面试常问到)

文章目录前言环形链表环形链表 II写在最后前言 本章的OJ练习相对于OJ练习(4)较为简单。不过&#xff0c;本章的OJ最重要的是要我们证明为何可以这么做。这也是面试中常出现的。 对于OJ练习(4)&#xff1a;-> 传送门 <-&#xff0c;分割链表以一种类似于归并的思想解得&a…

ChatGPT-4 终于来了(文末附免费体验地址)

大家好&#xff0c;我是小钱学长。 ChatGPT4.0 重磅来袭&#xff0c;今天一打开plus页面出现的就是这个GPT-4的体验界面&#xff01;现在就带大家一起看看GPT4.0​。 进入之后是这样的 看到最下面有一行话&#xff0c;目前应该是4个小时限制100条消息。 GPT-4有什么优势&…

手把手学会DFS (递归入门)

目录 算法介绍 递归实现指数型枚举 递归实现排列型枚举 递归实现组合型枚举 算法介绍 &#x1f9e9;DFS 即 Depth First Search &#xff0c;中文又叫深度优先搜索&#xff0c;是一种沿着树的深度对其进行遍历&#xff0c;直到尽头之后再进行回溯&#xff0c;再走其他路线的…

springboot复习(黑马)

学习目标基于SpringBoot框架的程序开发步骤熟练使用SpringBoot配置信息修改服务器配置基于SpringBoot的完成SSM整合项目开发一、SpringBoot简介1. 入门案例问题导入SpringMVC的HelloWord程序大家还记得吗&#xff1f;SpringBoot是由Pivotal团队提供的全新框架&#xff0c;其设计…

GPT-4技术报告

摘要 链接&#xff1a;https://cdn.openai.com/papers/gpt-4.pdf 我们汇报了GPT-4的发展&#xff0c;这是一个大规模的多模态模型&#xff0c;可以接受图像和文本输入并产生文本输出。虽然在许多现实场景中&#xff0c;GPT-4的能力不如人类&#xff0c;但它在各种专业和学术基…

数智链接,新一代校园招聘解决方案

疫情3年市场巨变&#xff0c;00后新生代初登上求职舞台&#xff0c;中和作用下&#xff0c;牛客发现新生代求职发生明显变化&#xff0c;企业校招也要随之而变&#xff0c;并率先提出以种草、精准、专业为特点的新一代校园招聘解决方案。01.学生求职变了&#xff01;安全感、非…

奇异值分解(SVD)原理与在降维中的应用

奇异值分解(SVD)原理与在降维中的应用 奇异值分解(Singular Value Decomposition&#xff0c;以下简称SVD)是在机器学习领域广泛应用的算法&#xff0c;它不光可以用于降维算法中的特征分解&#xff0c;还可以用于推荐系统&#xff0c;以及自然语言处理等领域。是很多机器学习算…

GPT-4来袭:开启人工智能新时代

文章目录介绍GPT4 模型演示示例示例 1示例 2示例 3示例 4示例 5最后Reference介绍 2023年3月15日&#xff0c;OpenAI公司正式发布了先进的自然语言处理模型GPT-4&#xff0c;前不久发布的GPT-3.5模型只能理解文字的语言模型&#xff0c;而新发布的GPT4则是多模态模型&#xff…

【java】了解常见集合类

了解常见集合类 一、集合类框架 1、集合类框架结构图 首先我们要对集合类结构有一个大体的认识&#xff0c;所有集合都继承于迭代器&#xff0c;分为单列集合和映射集合&#xff0c;单列集合分为有序可重复和有序不可重复&#xff0c;大概结构如下图所示 2、主要集合类的介…

你真的知道如何系统高效地学习数据结构与算法吗?

文章目录前言&#xff1a;什么是数据结构&#xff1f;什么是算法&#xff1f;学习这个算法需要什么基础&#xff1f;学习的重点在什么地方&#xff1f;一些可以让你事半功倍的学习技巧1.边学边练&#xff0c;适度刷题2.多问、多思考、多互动3.打怪升级学习法4.知识需要沉淀&…

文心一言---中国版的“ChatGPT”狂飙的机会或许要出现了

⭐️我叫忆_恒心&#xff0c;一名喜欢书写博客的在读研究生&#x1f468;‍&#x1f393;。 如果觉得本文能帮到您&#xff0c;麻烦点个赞&#x1f44d;呗&#xff01; 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧&#xff0c;喜欢的小伙伴给个三…

linux 基础

1.Shell 命令的格式如下&#xff1a;command -options [argument]command: Shell 命令名称。options&#xff1a; 选项&#xff0c;同一种命令可能有不同的选项&#xff0c;不同的选项其实现的功能不同。argument&#xff1a; Shell 命令是可以带参数的&#xff0c;也可以不带参…

【计算机二级Python】综合题目

计算机二级python真题 文章目录计算机二级python真题一、简单应用——明星投票二、综合应用题《评奖学金 两问》一、简单应用——明星投票 描述使用字典和列表型变量完成最有人气的明星的投票数据分析。投票信息由附件里的文件vote.txt给出,一行只有一个明星姓名的投票才是有效…

【BLE 5.3无线MCU CH582】1、初识CH582开发板(开箱)

1、认识板子 优点&#xff1a; &#xff08;1&#xff09;引脚全部引出&#xff1b; &#xff08;2&#xff09;USB下载程序&#xff1b; &#xff08;3&#xff09;TYPE-C接口好评&#xff1b; &#xff08;4&#xff09;板载连个两个USB口&#xff0c;都可以供电&#xff1b;…