【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)+N,N>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. 通用定时器输入捕获部分框图介绍 捕获/比较通道的输入部分(通道1) 采样频率:控制寄存器 1(TIMx_CR1)的CKD[1:0] ⬇⬇⬇滤波方式选择: 捕获/ 比较模式寄存器 1(TIMx_CCMR1)的输入捕获部分⬇⬇…...
Flask实现异步调用sqlalchemy的模型类
事情是这样的,我这边需要在一次请求里面,搞一个异步不阻碍的任务,来执行耗时的操作。 一开始,我准备写的代码是这样的: from flask import Flask import time from concurrent.futures import ThreadPoolExecutorexec…...
Pocket2Mol + Generation of Atom Positions生成原子位置的方法有什么?联合概率是什么?
联合概率: 联合概率是统计学中的一个概念,用于描述两个或多个随机事件同时发生的概率。当我们谈论多个变量的联合概率时,我们是在探讨这些变量同时取特定值的概率。 让我们简化一下概念: 假设你有一个骰子(六面&…...
区分手机小程序以及电脑小程序;左滑、导航键返回拦截
1、区分电脑小程序和手机小程序 //区分电脑小程序、手机小程序(目标:手机小程序) // #ifdef MP-WEIXIN uni.getSystemInfo({success: (res) > {// windows | mac为pc端// android | ios为手机端// console.log(getSystemInfo,, res.plat…...
Web APIs 2 事件
Web APIs 2 事件 事件监听案例:广告关闭案例:随机问答 事件监听版本事件类型案例:轮播图完整焦点事件键盘事件输入事件案例:评论字数统计 事件对象获取事件对象事件对象常用属性案例:评论回车发布 环境对象this回调函数…...
网易腾讯面试题精选----90道设计模式面试题及答案
介绍 设计模式是软件开发的重要组成部分,为常见设计问题提供经过验证的解决方案。就设计模式面试候选人可以帮助衡量他们对软件架构的理解、解决问题的能力以及编写可维护和可扩展代码的能力。以下是一些常见的设计模式面试问题和答案,可帮助评估候选人在该领域的知识和专业知…...
程序员的数字化工作台:理解不关机背后的逻辑与需求
目录 程序员为什么不喜欢关电脑? 电脑对程序员的重要性: 工作流程与需求: 数据安全与备份: 即时性与响应: 个人习惯等方面: 程序员为什么不喜欢关电脑? 电脑对程序员的重要性:…...
Java Socket Server TCP服务端向指定客户端发送消息
实现思路 首先需要知道java里如何创建一个Socket服务器端。 //创建一个服务器端对象ServerSocket server new ServerSocket(); //绑定启动的ip和端口号server.bind(new InetSocketAddress("127.0.0.1",8082));//启动成功后,调用accept()方法阻塞…...
java日志框架总结(五、logback日志框架)
一、logback概述 Logback是由log4j创始人设计的又一个开源日志组件。 Logback当前分成三个模块: 1、logback-core, 2、logback- classic 3、logback-access。 1)logback-core是其它两个模块的基础模块。 2)logback-…...
android下library打包aar并上传到maven,嵌入版的app
android嵌入版 准备工作简化代码到三方app上传maven自动打包上面已经完成了library到三方app的流程 这几天在研究android下怎么把自己的项目当作一个library给到另一个app做嵌入使用,把这些记录下来,方便以后参考 准备工作 1.需要了解一些gradle 命令打…...
Xampp中Xdebug的安装使用
工欲善其事,必先利其器 XDebug简介 XDebug 是一个用于 PHP 的调试和性能分析工具。它提供了一系列功能,帮助开发者在开发和调试 PHP 应用程序时更加高效。 以下是 XDebug 的一些主要特性和功能: 调试功能: 断点调试:…...
金融行业的软件测试分析
随着金融行业的业务不断增加,金融交易模式的不断变化,金融机构对信息化的要求也越来越高,高质量的金融软件对于金融机构来说显得尤为重要。如何保证金融行业软件的质量,对金融行业软件的测试人员来说,也提出了更高的要…...
踩坑了,MySQL数据库生成大量奇怪的大文件
作者:田逸(formyz) 一大早就收到某个数据库服务器磁盘满的报警信息,其中数据盘使用率超过90%,如下图所示。 这是一台刚上线不久的MySQL从库服务器,数据盘的总容量是300G。先登录系统,查看主从同…...
ctfshow-web11~20-WP
web11 根据提示,查询对ctfshow域名进行dns查询,查看TXT记录 阿里云查询链接:阿里云网站运维检测平台 获取flag成功 web12 根据题目提示,我们访问robots.txt,获取到后台地址 然后我们访问一下后台...
2.5学习总结9
并查集 知识点 并查集是一种数据结构,用于处理一些不相交集合的合并及查询问题。它支持两种操作: Find(x):查找元素 x 所属的集合。Union(x, y):将元素 x 所属的集合和元素 y 所属的集合合并。 初始化:将每个元素单…...
删除.git的影响、git分支切换时注意事项
一、删除.git的影响 master分支文件 dev分支文件 删除.git后 文件为删除.git前分支的文件状态。 二、git分支切换时注意事项 情景:如果我在分支A,想要跳转到分支B。 git的规矩是,在那个分支上进行的提交,就算哪个分支上的工作…...
Linux系统调试课:硬件断点
沉淀、分享、成长,让自己和他人都能有所收获!😄 📢在linux内核编程中,经常会遇到由于内存被篡改,例如 buffer overflow,野指针,write after free等。查找分析此类问题非常的麻烦。 一、什么是硬件断点 硬件断点,是Linux内核中是一种被ptrace和内核内调试器使用调试…...
百卓Smart管理平台 uploadfile.php 文件上传漏洞复现(CVE-2024-0939)
0x01 产品简介 百卓Smart管理平台是北京百卓网络技术有限公司(以下简称百卓网络)的一款安全网关产品,是一家致力于构建下一代安全互联网的高科技企业。 0x02 漏洞概述 百卓Smart管理平台 uploadfile.php 接口存在任意文件上传漏洞。未经身份验证的攻击者可以利用此漏洞上传…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...
用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法
用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...























