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

【Algorithms 4】算法(第4版)学习笔记 05 - 2.2 归并排序

文章目录

    • 前言
    • 参考目录
    • 学习笔记
      • 1:归并排序的简单演示
      • 1.1:基本思路
      • 1.2:归并排序的 demo 演示
      • 1.3:代码实现
      • 2:自顶向下的归并排序
      • 2.1:比较次数与访问次数的证明
      • 2.2:代码优化
      • 2.3:优化后代码实现
      • 3:自底向上的归并排序
      • 3.1:代码实现
      • 4:排序算法的复杂度
      • 5:稳定性
      • 5.1:插入排序:稳定
      • 5.2:选择排序:不稳定
      • 5.3:希尔排序:不稳定
      • 5.4:归并排序:稳定

前言

本章节主要内容是 归并排序,除此之外还有 排序算法的复杂度 以及 稳定性 的相关内容。

本章节中间有穿插说明 比较器(Compartor),不过本文暂且略过这一内容,感兴趣的朋友建议移步视频自行学习总结。

参考目录

  • B站 普林斯顿大学《Algorithms》视频课
    (请自行搜索。主要以该视频课顺序来进行笔记整理,课程讲述的教授本人是该书原版作者之一 Robert Sedgewick。)
  • 微信读书《算法(第4版)》
    (本文主要内容来自《2.2 归并排序》)
  • 官方网站
    (有书本配套的内容以及代码)

学习笔记

注1:下面引用内容如无注明出处,均是书中摘录。
注2:所有 demo 演示均为视频 PPT demo 截图。

1:归并排序的简单演示

1.1:基本思路

归并排序基本思路:

  • 数组一分为二
  • 每一半 递归 排序
  • 合并两半

在这里插入图片描述

1.2:归并排序的 demo 演示

对于归并排序,Sedgewick 教授的视频进行了分步演示,下面截图进行简单说明。

排好序的两个子数组:

在这里插入图片描述

在原数组的基础上复制一个辅助数组:

在这里插入图片描述

需要三个下标来进行操作:
i、j分别是两个比较的子数组的下标,k是原数组的下标。

比较两个子数组的数据,将较小的值放回原数组:

在这里插入图片描述

如果两个值相同,则将左侧子数组的值放回原数组:

在这里插入图片描述

如果其中一个子数组已经没有元素,则另一个子数组的元素直接放回原数组:

在这里插入图片描述

1.3:代码实现

edu.princeton.cs.algs4.Merge#merge

在这里插入图片描述

edu.princeton.cs.algs4.Merge#sort

在这里插入图片描述

2:自顶向下的归并排序

上面分步实现的归并排序是属于自顶向下的归并排序。官网给出了归并的分步结果图:

(截图自官网)
在这里插入图片描述

2.1:比较次数与访问次数的证明

比较次数和访问次数是衡量一个算法优劣与否的重要参考标准,因此这里给出了相关的证明。

(截图自视频 PPT)
在这里插入图片描述

每次归并最多需要访问数组6N次:

  • 2N次用来复制
  • 2N次用来将排好序的元素移动回去
  • 另外最多比较2N次

视频中,教授使用长度 N 为 2n 的数组来证明:
D ( N ) = 2 D ( N / 2 ) + N , N > 1 ,且 D ( 1 ) = 0 D(N) = 2D(N/2) + N,N>1,且 D(1) = 0 D(N)=2D(N/2)+NN>1,且D(1)=0

一共有三种证明方式,但说实话我看了几遍还是没太懂怎么算的(哭),先把证明方式贴出来:

方式一:图形法证明

在这里插入图片描述

方式二:数学方式证明

在这里插入图片描述

方式三:数学归纳法证明

在这里插入图片描述

这里再贴一下书里面的相关证明帮助理解:

在这里插入图片描述

命题F。对于长度为N的任意数组,自顶向下的归并排序需要½NlgN至NlgN次比较。

书中关于命题 F 的证明,相对来说容易理解一些,可以自行参考学习。

2.2:代码优化

归并排序虽然速度比较快,但是也有一些缺点,因此也提出了一些优化方案:(这里列出对应的章节)

  • 2.2.2.1 对小规模子数组使用插入排序
  • 2.2.2.2 测试数组是否已经有序
  • 2.2.2.3 不将元素复制到辅助数组

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

2.3:优化后代码实现

edu.princeton.cs.algs4.MergeX#sort

在这里插入图片描述

3:自底向上的归并排序

自顶向下的归并排序使用了递归的方式,为了减少递归的操作,又提出了自底向上的归并排序。

(截图自官网)
在这里插入图片描述

3.1:代码实现

edu.princeton.cs.algs4.MergeBU#sort

在这里插入图片描述

4:排序算法的复杂度

这里使用了决策树来进行说明,不过我觉得这一部分书本的说明不是很好,有些地方说得云里雾里的……

例如:

在这里插入图片描述

一眼看过去不知道是啥。然后看教授的PPT:

在这里插入图片描述

还有对于命题 I 的描述,每一个字我都认识,愣是读了好几遍才读通顺:

命题I。没有任何基于比较的算法能够保证使用少于lg(N!)~NlgN次比较将长度为N的数组排序。

再来看看视频里是怎么说的:

Any compare-based sorting algorithm must use at least lg(N!)~NlgN compares in the worst-case.
任何基于比较的排序算法,在最坏的情况下需要使用 lg(N!)~NlgN 次比较。

贴一下完整的 PPT 截图,一目了然:

在这里插入图片描述

证明:

  • 假设数组由N个不同的值 a1 到 aN 组成。
  • 最坏的情况由决策树的 高度 h 决定。
  • 高度为 h 的二叉树最多有 2h 叶子节点。
  • N! 不同的排序 => 至少 N! 叶子节点。

根据书里面的说明再完善一下:

从比较树观察得到的第一个重要结论是这棵树应该至少有 N! 个叶子结点,因为 N 个不同的主键会有 N! 种不同的排列。


二叉树的一个基本的组合学性质就是高度为 h 的树最多只可能有 2h 个叶子结点,拥有 2h 个结点的树是完美平衡的,或称为完全树。

在这里插入图片描述

5:稳定性

这一部分回顾了目前所讲到的四种算法:插入排序、选择排序、希尔排序以及归并排序。

Q:哪些算法是稳定的?
A:插入排序和归并排序。(选择排序和希尔排序不稳定。)

5.1:插入排序:稳定

在这里插入图片描述

插入排序中,相同的值不会越过彼此。

通常而言,看一个排序是否稳定,一般是看它是否有长距离的交换可能使得一条记录越过某一条相同值的记录。

5.2:选择排序:不稳定

在这里插入图片描述

5.3:希尔排序:不稳定

在这里插入图片描述

5.4:归并排序:稳定

只要归并操作是稳定的,那么归并排序算法就是稳定的;操作是否稳定,取决于代码怎么写。

在这里插入图片描述

(完)

相关文章:

【Algorithms 4】算法(第4版)学习笔记 05 - 2.2 归并排序

文章目录 前言参考目录学习笔记1:归并排序的简单演示1.1:基本思路1.2:归并排序的 demo 演示1.3:代码实现2:自顶向下的归并排序2.1:比较次数与访问次数的证明2.2:代码优化2.3:优化后代…...

mybatis mapper sql include用法实现sql块复用

一、总SQL <select id"getxxxMonitorData"resultType"com.xxx.module.system.dal.dataobject.xxx.xxxDO"><include refid"getxxxMonitorDataBaseSql"></include><include refid"whereContent"></include&…...

正点原子--STM32通用定时器学习笔记(2)

1. 通用定时器输入捕获部分框图介绍 捕获/比较通道的输入部分&#xff08;通道1&#xff09; 采样频率&#xff1a;控制寄存器 1(TIMx_CR1)的CKD[1:0] ⬇⬇⬇​​​​​​​滤波方式选择&#xff1a; 捕获/ 比较模式寄存器 1(TIMx_CCMR1)的输入捕获部分⬇​​​​​​​⬇​…...

Flask实现异步调用sqlalchemy的模型类

事情是这样的&#xff0c;我这边需要在一次请求里面&#xff0c;搞一个异步不阻碍的任务&#xff0c;来执行耗时的操作。 一开始&#xff0c;我准备写的代码是这样的&#xff1a; from flask import Flask import time from concurrent.futures import ThreadPoolExecutorexec…...

Pocket2Mol + Generation of Atom Positions生成原子位置的方法有什么?联合概率是什么?

联合概率&#xff1a; 联合概率是统计学中的一个概念&#xff0c;用于描述两个或多个随机事件同时发生的概率。当我们谈论多个变量的联合概率时&#xff0c;我们是在探讨这些变量同时取特定值的概率。 让我们简化一下概念&#xff1a; 假设你有一个骰子&#xff08;六面&…...

区分手机小程序以及电脑小程序;左滑、导航键返回拦截

1、区分电脑小程序和手机小程序 //区分电脑小程序、手机小程序&#xff08;目标&#xff1a;手机小程序&#xff09; // #ifdef MP-WEIXIN uni.getSystemInfo({success: (res) > {// windows | mac为pc端// android | ios为手机端// console.log(getSystemInfo,, res.plat…...

Web APIs 2 事件

Web APIs 2 事件 事件监听案例&#xff1a;广告关闭案例&#xff1a;随机问答 事件监听版本事件类型案例&#xff1a;轮播图完整焦点事件键盘事件输入事件案例&#xff1a;评论字数统计 事件对象获取事件对象事件对象常用属性案例&#xff1a;评论回车发布 环境对象this回调函数…...

网易腾讯面试题精选----90道设计模式面试题及答案

介绍 设计模式是软件开发的重要组成部分,为常见设计问题提供经过验证的解决方案。就设计模式面试候选人可以帮助衡量他们对软件架构的理解、解决问题的能力以及编写可维护和可扩展代码的能力。以下是一些常见的设计模式面试问题和答案,可帮助评估候选人在该领域的知识和专业知…...

程序员的数字化工作台:理解不关机背后的逻辑与需求

目录 程序员为什么不喜欢关电脑&#xff1f; 电脑对程序员的重要性&#xff1a; 工作流程与需求&#xff1a; 数据安全与备份&#xff1a; 即时性与响应&#xff1a; 个人习惯等方面&#xff1a; 程序员为什么不喜欢关电脑&#xff1f; 电脑对程序员的重要性&#xff1a;…...

Java Socket Server TCP服务端向指定客户端发送消息

实现思路 首先需要知道java里如何创建一个Socket服务器端。 //创建一个服务器端对象ServerSocket server new ServerSocket(); //绑定启动的ip和端口号server.bind(new InetSocketAddress("127.0.0.1",8082));//启动成功后&#xff0c;调用accept()方法阻塞&#xf…...

java日志框架总结(五、logback日志框架)

一、logback概述 Logback是由log4j创始人设计的又一个开源日志组件。 Logback当前分成三个模块&#xff1a; 1、logback-core, 2、logback- classic 3、logback-access。 1&#xff09;logback-core是其它两个模块的基础模块。 2&#xff09;logback-…...

android下library打包aar并上传到maven,嵌入版的app

android嵌入版 准备工作简化代码到三方app上传maven自动打包上面已经完成了library到三方app的流程 这几天在研究android下怎么把自己的项目当作一个library给到另一个app做嵌入使用&#xff0c;把这些记录下来&#xff0c;方便以后参考 准备工作 1.需要了解一些gradle 命令打…...

Xampp中Xdebug的安装使用

工欲善其事&#xff0c;必先利其器 XDebug简介 XDebug 是一个用于 PHP 的调试和性能分析工具。它提供了一系列功能&#xff0c;帮助开发者在开发和调试 PHP 应用程序时更加高效。 以下是 XDebug 的一些主要特性和功能&#xff1a; 调试功能&#xff1a; 断点调试&#xff1a;…...

金融行业的软件测试分析

随着金融行业的业务不断增加&#xff0c;金融交易模式的不断变化&#xff0c;金融机构对信息化的要求也越来越高&#xff0c;高质量的金融软件对于金融机构来说显得尤为重要。如何保证金融行业软件的质量&#xff0c;对金融行业软件的测试人员来说&#xff0c;也提出了更高的要…...

踩坑了,MySQL数据库生成大量奇怪的大文件

作者&#xff1a;田逸&#xff08;formyz&#xff09; 一大早就收到某个数据库服务器磁盘满的报警信息&#xff0c;其中数据盘使用率超过90%&#xff0c;如下图所示。 这是一台刚上线不久的MySQL从库服务器&#xff0c;数据盘的总容量是300G。先登录系统&#xff0c;查看主从同…...

ctfshow-web11~20-WP

web11 根据提示,查询对ctfshow域名进行dns查询,查看TXT记录 阿里云查询链接:阿里云网站运维检测平台 获取flag成功 web12 根据题目提示,我们访问robots.txt,获取到后台地址 然后我们访问一下后台...

2.5学习总结9

并查集 知识点 并查集是一种数据结构&#xff0c;用于处理一些不相交集合的合并及查询问题。它支持两种操作&#xff1a; Find(x)&#xff1a;查找元素 x 所属的集合。Union(x, y)&#xff1a;将元素 x 所属的集合和元素 y 所属的集合合并。 初始化&#xff1a;将每个元素单…...

删除.git的影响、git分支切换时注意事项

一、删除.git的影响 master分支文件 dev分支文件 删除.git后 文件为删除.git前分支的文件状态。 二、git分支切换时注意事项 情景&#xff1a;如果我在分支A&#xff0c;想要跳转到分支B。 git的规矩是&#xff0c;在那个分支上进行的提交&#xff0c;就算哪个分支上的工作…...

Linux系统调试课:硬件断点

沉淀、分享、成长,让自己和他人都能有所收获!😄 📢在linux内核编程中,经常会遇到由于内存被篡改,例如 buffer overflow,野指针,write after free等。查找分析此类问题非常的麻烦。 一、什么是硬件断点 硬件断点,是Linux内核中是一种被ptrace和内核内调试器使用调试…...

百卓Smart管理平台 uploadfile.php 文件上传漏洞复现(CVE-2024-0939)

0x01 产品简介 百卓Smart管理平台是北京百卓网络技术有限公司(以下简称百卓网络)的一款安全网关产品,是一家致力于构建下一代安全互联网的高科技企业。 0x02 漏洞概述 百卓Smart管理平台 uploadfile.php 接口存在任意文件上传漏洞。未经身份验证的攻击者可以利用此漏洞上传…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

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

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

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...