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

归并排序和快速排序的两种实现

在此之前我们已经介绍过归并排序和快速排序:浅谈归并排序与快速排序,但其中的实现都是基于递归的。本文将重新温故这两种算法并给出基于迭代的实现。

目录

  • 1. 归并排序
    • 1.1 基于递归
    • 1.2 基于迭代
  • 2. 快速排序
    • 2.1 基于递归
    • 2.2 基于迭代

1. 归并排序

1.1 基于递归

归并排序的核心是二路归并,实现二路归并需要一个额外的辅助数组,因此空间复杂度是 O ( n ) O(n) O(n)

void merge(vector<int>& a, int l, int mid, int r, vector<int>& tmp) {int i = l, j = mid + 1, k = l;while (i <= mid && j <= r) {if (a[i] <= a[j]) tmp[k++] = a[i++];else tmp[k++] = a[j++];}while (i <= mid) tmp[k++] = a[i++];while (j <= r) tmp[k++] = a[j++];for (int i = l; i <= r; i++) a[i] = tmp[i];
}

该函数会对数组 a[l, mid][mid + 1, r] 两部分进行二路归并,其中辅助数组 tmp 的大小与 a 相同。

有了 merge 函数,我们就可以很方便的实现归并排序了:

void merge_sort(vector<int>& a, int l, int r, vector<int>& tmp) {if (l >= r) return;int mid = l + r >> 1;merge_sort(a, l, mid, tmp), merge_sort(a, mid + 1, r, tmp);merge(a, l, mid, r, tmp);
}

1.2 基于迭代

很明显,基于递归的实现是自顶向下的,而基于迭代的实现是自底向上的。

我们可以先枚举区间长度,再枚举区间左端点。一开始每个区间的长度是 1 1 1,我们每次对相邻的两个区间进行二路归并,每归并一次区间的长度就是原先的两倍,所以枚举区间长度时变量 len 的更新方式为 len *= 2

对于区间左端点,每合并完两个区间后,左端点就要更新成下下个区间,如下图所示:

还需保证 mid < n - 1,即 l < n - len

void merge_sort(vector<int>& a) {int n = a.size();vector<int> tmp(n);for (int len = 1; len < n; len *= 2) {for (int l = 0; l < n - len; l += 2 * len) {int mid = l + len - 1;int r = min(l + 2 * len - 1, n - 1);merge(a, l, mid, r, tmp);}}
}

归并排序的时间复杂度是 O ( n log ⁡ n ) O(n\log n) O(nlogn),无论是递归还是迭代,空间复杂度都是 O ( n ) O(n) O(n)

2. 快速排序

2.1 基于递归

void quick_sort(vector<int>& a, int l, int r) {if (l >= r) return;int mid = l + r >> 1;int i = l - 1, j = r + 1, x = a[mid];while (i < j) {while (a[++i] < x);while (a[--j] > x);if (i < j) swap(a[i], a[j]);}quick_sort(a, l, j), quick_sort(a, j + 1, r);
}

2.2 基于迭代

void quick_sort(vector<int>& a, int l, int r) {if (l >= r) return;stack<pair<int, int>> stk;stk.emplace(l, r);while (!stk.empty()) {auto [l, r] = stk.top();stk.pop();if (l < r) {int mid = l + r >> 1;int i = l - 1, j = r + 1, x = a[mid];while (i < j) {while (a[++i] < x);while (a[--j] > x);if (i < j) swap(a[i], a[j]);}stk.emplace(l, j);stk.emplace(j + 1, r);}}
}

时间复杂度是 O ( n log ⁡ n ) O(n\log n) O(nlogn),空间复杂度是 O ( log ⁡ n ) O(\log n) O(logn)

相关文章:

归并排序和快速排序的两种实现

在此之前我们已经介绍过归并排序和快速排序&#xff1a;浅谈归并排序与快速排序&#xff0c;但其中的实现都是基于递归的。本文将重新温故这两种算法并给出基于迭代的实现。 目录 1. 归并排序1.1 基于递归1.2 基于迭代 2. 快速排序2.1 基于递归2.2 基于迭代 1. 归并排序 1.1 基…...

C#,《小白学程序》第十四课:随机数(Random)第一,几种随机数的计算方法与代码

1 文本格式 /// <summary> /// 《小白学程序》第十四课&#xff1a;随机数&#xff08;Random&#xff09;第一&#xff0c;几种随机数的计算方法与代码 /// 本课初步接触一下随机数。 /// </summary> /// <param name"sender"></param> ///…...

[杂谈]-快速了解Modbus协议

快速了解Modbus协议 文章目录 快速了解Modbus协议1、为何 Modbus 如此受欢迎2、范围和数据速率3、逻辑电平4、层数5、网络与通讯6、数据帧格式7、数据类型8、服务器如何存储数据9、总结 ​ Modbus 是一种流行的低速串行通信协议&#xff0c;广泛应用于自动化行业。 该协议由 Mo…...

WhatsApp的两个商业模式该如何选择

WhatsApp Business 是什么 目前 WhatsApp 提供两种商业模式&#xff0c;企业应根据自身需求选择相应版本。 第一个版本是 WhatsApp Business&#xff1a;初创企业只需一个手机应用程序&#xff0c;便可以个体单位与客户轻松互动; 另一个版本是 WhatsApp Business API&#xff…...

动态表单设计

动态表单设计 背景方案讨论基于上面分析&#xff0c;对比调研&#xff0c;自定义动态表单数据模型表单详解&#xff08;一&#xff09; 表单模板&#xff1a;jim_dynamic_form&#xff08;二&#xff09;表单数据类型&#xff1a;jim_form_data_type&#xff08;三&#xff09;…...

JAR will be empty - no content was marked for inclusion!

现象 在对自建pom依赖组件打包时&#xff0c;出现JAR will be empty - no content was marked for inclusion!错误。 方案 在pom中怎么加packaging标签内容为pom&#xff0c;标识只打包pom文件 <?xml version"1.0" encoding"UTF-8"?> ...<grou…...

软件生命周期及流程【软件测试】

软件的生命周期 软件生命周期是软件开始研制到最终被废弃不用所经历的各个阶段。 瀑布型生命周期模型 规定了它们自上而下、相互衔接的固定次序&#xff0c;如同瀑布流水&#xff0c;逐级下落&#xff0c;具有顺序性和依赖性。每个阶段规定文档并需进行评审。 特点&#xff…...

2023高教社杯数学建模E题思路代码 - 黄河水沙监测数据分析

# 1 赛题 E 题 黄河水沙监测数据分析 黄河是中华民族的母亲河。研究黄河水沙通量的变化规律对沿黄流域的环境治理、气候变 化和人民生活的影响&#xff0c; 以及对优化黄河流域水资源分配、协调人地关系、调水调沙、防洪减灾 等方面都具有重要的理论指导意义。 附件 1 给出了位…...

双翌保养码使用指南方法(一)

保养码使用指南一 为了确保软件的正常运行和有效使用&#xff0c;正确地使用保养码是至关重要的。以下是保养码使用的简单指南&#xff0c;以帮助您进行正确的操作。 1. 打开软件入口&#xff1a;首先&#xff0c;在您的电脑上打开文件夹&#xff0c;并找到s-y softactive tool…...

hive指定字段插入数据,包含了分区表和非分区表

1、建表 语句如下&#xff1a; CREATE EXTERNAL TABLE ods_lineitem_full (l_shipdate date,l_orderkey bigint,l_linenumber int,l_partkey int,l_suppkey int,l_quantity decimal(15, 2),l_extendedprice decimal(15, 2),l_discount de…...

浏览器端vscode docker搭建(附带python环境)

dockerfile from centos:7 #安装python环境 run yum -y install wget openssl-devel bzip2-devel expat-devel gdbm-devel readline-devel zlib-devel libffi-devel gcc make run wget https://www.python.org/ftp/python/3.9.0/Python-3.9.0.tgz run tar -xvf Python-3.9.…...

Echarts图表跟随父容器的变化自适应

如果页面中有多个图表 隐藏/展开左边侧边栏echarts图表自适应 <div class"line"><div class"title">制冷站关键参数</div><div id"chartLine1" style"width: 100%;height:85%;"></div></div><…...

【多线程】ThreadLocal是什么?有哪些使用场景?使用ThreadLocal需要注意些什么?

文章目录 前言一、ThreadLocal 是什么&#xff1f;二、有哪些使用场景&#xff1f;三、实现原理四、在线程池中使用 ThreadLocal 为什么可能导致内存泄露呢&#xff1f;五、线程池中&#xff0c;如何正确使用 ThreadLocal&#xff1f;六、ThreadLocal 核心方法 前言 一、Threa…...

一种基于动态代理的通用研发提效解决方案

作为一名研发人员&#xff0c;除了业务开发之外&#xff0c;研发提效是一个永恒的话题&#xff0c;而女娲正是这一话题下进行的一次全面的剖析和实践。 作者&#xff1a;张全洪(钝悟) 一、女娲是什么 女娲是业务研发同学&#xff08;开发、测试、运维&#xff09;在软件迭代的…...

【vue3】一些关于hooks的使用经验

前言 最近接到了一个需求&#xff0c;隔壁嵌入式部门希望我们用前端解析渲染Kconfig表单。这篇文章用来记录一下本次使用hook pinia vue3的经验 hooks hooks的概念最早是在 React 中听到的&#xff0c;虽然早些时间也写过一点react&#xff0c;但也只是照葫芦画瓢&#xf…...

面试系列 - Java 并发容器详解

Java 并发容器是一组用于在多线程环境下安全访问和操作数据的数据结构。它们提供了线程安全的集合和映射&#xff0c;使开发者能够更轻松地处理并发编程问题。 一、Java并发容器 ConcurrentHashMap&#xff1a; 它是一个高效的并发哈希表&#xff0c;支持多线程并发操作而不需…...

使用动态住宅代理还能带来哪些好处?

一、什么是动态住宅代理ip 动态住宅代理是一种代理技术&#xff0c;它利用代理服务器中转用户和目标服务器之间的网络流量&#xff0c;实现用户真实位置的屏蔽。代理提供商会有自己的ip大池子&#xff0c;当你通过代理服务器向网站发送请求时&#xff0c;服务器会从池子中选中…...

笙默考试管理系统-MyExamTest----codemirror(18)

笙默考试管理系统-MyExamTest----codemirror&#xff08;18&#xff09; 目录 一、 笙默考试管理系统-MyExamTest----codemirror 二、 笙默考试管理系统-MyExamTest----codemirror 三、 笙默考试管理系统-MyExamTest----codemirror 四、 笙默考试管理系统-MyExamTest---…...

TGA格式文件转材质

今天淘宝上买了一个美女的模型&#xff0c;是blender的源文件&#xff0c;上面说有fbx格式的。我用unity&#xff0c;所以觉得应该可以用。文件内容如下图&#xff1a; FBX文件夹打开后&#xff0c;内容如下图所示&#xff0c;当时就预感到可能没有色彩。 unity打开后果然发现只…...

IP应用场景查询API:深入了解网络用户行为的利器

前言 随着数字时代的不断发展&#xff0c;互联网已经成为人们生活的重要组成部分。而随着越来越多的业务和社交活动迁移到在线平台上&#xff0c;了解和理解网络用户行为变得至关重要。为了满足这个需求&#xff0c;IP 应用场景查询 API 崭露头角&#xff0c;成为深入了解网络…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

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

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

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

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

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

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...