当前位置: 首页 > 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 接口存在任意文件上传漏洞。未经身份验证的攻击者可以利用此漏洞上传…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...