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

C++学习笔记（三十六）——STL之排序算法

news 来源：原创 2025/7/19 21:13:11

一、STL 算法

C++的STL（Standard Template Library） 提供了一组高效、通用的算法，这些算法适用于各种容器（如 vector、list、set、map）。
这些算法主要位于 <algorithm> 和 <numeric> 头文件中。

通用性：适用于所有 STL 容器，如 vector、list、deque 等。
高效性：内部使用优化算法（如快速排序 std::sort）。
一致性：所有算法都基于迭代器操作，使其与不同容器兼容。
可组合性：可结合 lambda 表达式、bind、function object 使用。

二、STL 算法分类

STL 算法可分为以下几类：

类别	常见算法	作用
排序	`sort`、`stable_sort`、`partial_sort`、`nth_element`等	排序
搜索	`find`、`find_if`、`count`、`count_if`、`binary_search`等	查找元素
修改	`copy`、`replace`、`replace_if`、`swap`、`fill`等	修改容器内容
删除	`remove`、`remove_if`、`unique`等	删除元素
归约	`for_each`、`accumulate`等	处理数据
合并	`merge`、`set_union`、`set_intersection`等	处理有序序列
排列组合	`next_permutation`、`prev_permutation`等	生成排列
堆操作	`push_heap`、`pop_heap`、`make_heap`、`sort_heap`等	处理堆

三、STL 排序算法

STL 提供了一些常用的排序算法，用于对容器中的元素进行排序。
它们位于 <algorithm> 头文件中。

算法名称	功能描述	时间复杂度	空间复杂度	使用场景
`sort`	对容器元素进行排序（默认升序）	O(n log n)	O(log n)	适合一般排序，且不关心相等元素顺序
`stable_sort`	保证相等元素的顺序不变	O(n log n)	O(n)	适合需要稳定排序的场景，如多次排序
`partial_sort`	仅对前 `n` 个元素排序	O(n log k)	O(n)	只需要排序最小的 `n` 个元素
`nth_element`	对第 `n` 小元素进行排序，且两侧有序	O(n)	O(1)	寻找第 `n` 小元素，适合大数据情况
`reverse`	反转容器元素的顺序	O(n)	O(1)	用于反转容器，常与排序结合使用

（1） `sort`

功能：对容器中的元素进行排序，默认按升序排序。
时间复杂度：O(n log n)（平均和最坏情况）。
空间复杂度：O(log n)（递归调用栈空间）。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = {5, 2, 8, 3, 1};sort(vec.begin(), vec.end());for (int i : vec) {std::cout << i << " ";  // 输出：1 2 3 5 8}cout << endl;system("pause");return 0;
}

注意：

sort是最常用的排序算法，排序速度较快，但不能保证相等元素的顺序不变。

（2） `stable_sort`

功能：与 sort 相似，但保证相等元素的相对顺序不变。
时间复杂度：O(n log n)（与 sort 相同）。
空间复杂度：O(n)（通常需要额外空间用于稳定性保证）。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 5, 2, 8, 3, 5 };stable_sort(vec.begin(), vec.end());for (int i : vec) {cout << i << " ";  // 输出：2 3 5 5 8}cout << endl;system("pause");return 0;
}

注意：

stable_sort适用于需要保留相等元素顺序的场景，如按照多个条件排序时。

（3）`partial_sort`

功能：对容器中的前 n 个元素进行排序，使它们排好序，其他元素保持原顺序。
时间复杂度：O(n log k)，其中 n 是需要排序的元素数目，k 容器中的元素总数。
空间复杂度：O(n)。
说明：适用于只需要获取最小（或最大）n 个元素的情况。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 5, 2, 8, 3, 1 };// 排序前3个元素partial_sort(vec.begin(), vec.begin() + 3, vec.end());for (int i : vec) {cout << i << " ";  // 输出：1 2 3 8 5}cout << endl;system("pause");return 0;
}

注意：

partial_sort适用于只需要获取最小（或最大）n 个元素的情况。

（4）`nth_element`

功能：将容器中的元素按照第 n 小元素排列，使得第 n 小元素的左边小于等于它，右边大于等于它。
时间复杂度：O(n)，即线性时间复杂度。
空间复杂度：O(1)。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 5, 2, 8, 3, 1 };// 将第3小的元素放到第3位置，且两侧元素满足排序条件nth_element(vec.begin(), vec.begin() + 2, vec.end());for (int i : vec) {cout << i << " ";  // 输出：1 2 3 5 8}cout << endl;system("pause");return 0;
}

注意：

nth_element通常用于找到容器中的第 n 小（或大）元素，不需要完全排序。

（5）`reverse`

功能：反转容器中元素的顺序。
时间复杂度：O(n)，n 是容器中的元素数目。
空间复杂度：O(1)，原地操作。

示例：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>int main() {vector<int> vec = { 1, 2, 3, 4, 5 };// 反转数组reverse(vec.begin(), vec.end());for (int i : vec) {cout << i << " ";  // 输出：5 4 3 2 1}cout << endl;system("pause");return 0;
}

注意：

reverse用于反转容器中的元素，常用于从降序排序转换为升序排序。

C++学习笔记（三十六）——STL之排序算法

一、STL 算法 C的STL（Standard Template Library） 提供了一组高效、通用的算法，这些算法适用于各种容器（如 vector、list、set、map）。这些算法主要位于 <algorithm> 和 <numeric> 头文件中。通用性&a…...

编程日记 2025/7/19 21:13:11

G1 人形机器人软件系统架构与 Python SDK

如果说人形机器人的硬件是它的“身体”，那么软件系统就是它的“大脑”和“神经系统”，负责接收信息、进行决策并控制身体行动。理解 G1 机器人的软件架构，特别是如何通过编程接口与其交互，是进行机器人开发的核心。本节将剖析 G1 …...

编程日记 2025/7/20 3:48:40

Redis在SpringBoot中的使用

在SpringBoot项目中使用redis存储数据作为字典本项目使用jdk1.8 一、添加依赖  <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId>…...

编程日记 2025/6/29 9:41:10

SuperMap GIS基础产品FAQ集锦(20250421)

一、SuperMap iDesktopX 问题1：iDesktopX怎么根据对数据集中的每条记录进行批量布局出图? 11.3.0 【解决办法】打开地图系列设置功能，勾选启用并设置索引地图，索引图层和索引字段等参数，打印地图册，设置输出路径&am…...

编程日记 2025/7/20 3:59:02

Linux学习笔记2

1.man man指令相当于一个在线手册使用q可以退出指令运行例如，使用 man ls 指令可以得到以下运行结果： 在查找的时候还可以使用数字，使用 man man 指令，对应每个数字所表示的内容： 在Linux下，一切皆是文件…...

编程日记 2025/6/29 9:47:08

1.下载adb工具下载地址： https://developer.android.google.cn/tools/releases/platform-tools?hlzh-cn#downloads 根据需要下载自己系统需要的安装包下载后解压 2.配置adb工具环境变量添加ADB_HOME D:\softwares\platform-tools-latest-windows\platform-…...

编程日记 2025/7/20 3:56:31

EAL4+与等保2.0：解读中国网络安全双标准

EAL4与等保2.0：解读中国网络安全双标准在当今数字化时代，网络安全已成为各个行业不可忽视的重要议题。特别是在金融、政府、医疗等领域，保护信息的安全性和隐私性显得尤为关键。在中国，EAL4和等级保护2.0（简称“等保…...

编程日记 2025/6/29 10:31:50

树莓派学习专题＜8＞：使用V4L2驱动获取摄像头数据--获取摄像头支持的分辨率

树莓派学习专题＜8＞：使用V4L2驱动获取摄像头数据--获取摄像头支持的分辨率 1. 获取摄像头支持的分辨率2. 代码分析3. 树莓派实测 1. 获取摄像头支持的分辨率使用如下代码获取摄像头支持的输出分辨率。 struct v4l2_frmsizeenum stFrameSize …...

编程日记 2025/7/20 3:49:59

CSS预处理器对比：Sass、Less与Stylus如何选择

引言 CSS预处理器已成为现代前端开发的标准工具，它们通过添加编程特性来增强纯CSS的功能，使样式表更加模块化、可维护且高效。在众多预处理器中，Sass、Less和Stylus是三个最流行的选择，它们各自拥有独特的语法和功能特点。本文将深…...

编程日记 2025/7/20 3:52:35

Vue3集成sass

安装依赖 pnpm add -D sass-embedded配置全局变量新建文件 src/styles/variables.scss配置Vite 修改 vite.config.ts variables.scss $base-color: bluevite.config.ts // https://vite.dev/config/ export default defineConfig({plugins: [vue(),],resolve: {alias: {:…...

编程日记 2025/7/20 3:25:01

超越Dify工作流：如何通过修改QwenAgent的Function Call及ReAct方法实现对日期时间的高效意图识别

在构建复杂的AI应用时，意图识别是一个至关重要的环节。传统上，许多开发者会使用Dify工作流来完成这一任务，但在处理复杂意图时，这种方法往往需要大模型进行多级反复识别，从而带来较高的时间成本。本文将介绍如何通过修改QwenAgent框架中的FnCallAgent和ReActChat类，实现…...

编程日记 2025/7/20 3:47:25

Lua 第8部分补充知识

8.1 局部变量和代码块 Lua 语言中的变量在默认情况下是全局变量 ，所有的局部变量在使用前必须声明。与全局变量不同，局部变量的生效范围仅限于声明它的代码块。一个代码块（ block ）是一个控制结构的主体，或是一个函…...

编程日记 2025/7/20 3:31:55

Lua 第7部分输入输出

由于 Lua 语言强调可移植性和嵌入性 ， 所以 Lua 语言本身并没有提供太多与外部交互的机制。在真实的 Lua 程序中，从图形、数据库到网络的访问等大多数 I/O 操作，要么由宿主程序实现，要么通过不包括在发行版中的外部库实现。单就…...

编程日记 2025/7/15 15:28:22

Java 中 == 和 equals() 的区别

1. 运算符是 Java 中的比较运算符，用于比较两个变量的值是否相等，但具体行为取决于变量的类型： 类型比较的内容基本类型直接比较值是否相等（如 int a 5; int b 5; a b 返回 true）引用类型比较内存地址&#x…...

编程日记 2025/6/29 9:38:02

Redis新节点加入集群会发生什么（面试题）

新加入主节点：会发生槽位数据重新分配迁移， 新加入从节点，会发生主从同步，全量同步和增量同步当一个新节点加入 Redis 集群时，会触发一系列操作以确保集群的稳定性和数据的一致性。以下是新节点加入 Redis 集群时的详…...

编程日记 2025/6/29 10:59:22

dmncdm达梦新云缓存数据库主从集群安装部署详细步骤说明

dmncdm达梦新云缓存数据库主从集群安装部署详细步骤说明 1 环境介绍2 安装部署dmncdm2.1 196部署cdm环境2.2 197部署cdm环境2.3 190部署cdm环境 3 主备集群/主从集群配置4 部署主备集群/主从集群5 部署日志6 更多达梦数据库全方位指南:安装优化与实战教程 1 环境介绍 cpu x8…...

编程日记 2025/6/29 12:08:31

docker容器，mysql的日志文件怎么清理

访问问题你的问题是因为在当前路径 /home/ictrek/data/ragflow-mysql 下没有名为 data 的子目录。以下是详细分析和解决方法： 错误原因路径不存在当前目录 /home/ictrek/data/ragflow-mysql 下没有名为 data 的子目录，执行 cd data/ 时会报错 No suc…...

编程日记 2025/6/29 9:37:01

kafka auto.offset.reset详解

在 Kafka 中，auto.offset.reset latest 的含义及行为如下： 1. 核心定义当消费者组首次启动或无法找到有效的 offset（例如 offset 过期、被删除或从未提交）时，消费者会从分区的最新位置…...

编程日记 2025/6/29 9:37:21

设备制造行业如何避免项目管理混乱？

项目常因进度延误、成本超支或部门协作不畅而陷入混乱？ 这不仅拖累项目交付，还可能损害客户信任和企业利润。设备制造行业的项目管理复杂多变，从需求获取到生产交付再到售后运维，每一个环节都可能成为效率的瓶颈。如何破解这一…...

编程日记 2025/6/29 11:17:04

kubernetes》》k8s》》删除命名空间

使用 kubectl delete ns 命名空间 --force --grace-period0 如果还删除不掉需要 kubectl get namespace 命名空间 -o json > x.json vim x.json kubectl replace --raw “/api/v1/namespaces/命名空间/finalize” -f ./x.json...

编程日记 2025/6/29 11:33:46

【深度学习新浪潮】新视角生成的研究进展调研报告（2025年4月）

新视角生成（Novel View Synthesis）是计算机视觉与图形学领域的核心技术，旨在从单张或稀疏图像中生成任意视角的高保真图像，突破传统多视角数据的限制，实现对三维场景的自由探索。作为计算机视觉与图形学的交叉领域，近新视角生成年来在算法创新、应用落地和工具生态上均取…...

编程日记 2025/6/29 9:37:49

55、Spring Boot 详细讲义（十一项目实战）springboot应用的登录功能和权限认证

项目文档：springboot应用的登录功能和权限认证一、项目概述 1. 项目简介本项目是在一个基于Spring Boot的Web应用中实现登录功能和权限认证。要求实现登录功能，用户登录成功以后，会给前台返回当前登录用户可以访问的权限菜单，比如超级管理员可以访问所有权限，产品管理…...

编程日记 2025/6/29 9:38:03

react 父子组件通信子直接到父，父 forwardref子

React核心概念：单向数据流（Unidirectional Data Flow） React 中数据的流动像瀑布一样，只能从上层组件（父组件）流向下层组件（子组件）。子组件无法直接反向修改父组件的数据&#x…...

编程日记 2025/6/29 10:58:44

基于TCP的协议

目录 TCP 基于TCP的应用层协议： TCP的工作方式 TCP TCP（传输控制协议）是一种面向连接的、可靠的、基于字节流的传输层协议。它为应用层提供了一个可靠的端到端的数据传输服务。再TCP/IP模型中，TCP位于传输层，负责再…...

编程日记 2025/7/2 19:22:17

性能比拼: Go vs Java

本内容是对知名性能评测博主 Anton Putra Go (Golang) vs Java: Performance Benchmark 内容的翻译与整理, 有适当删减, 相关指标和结论以原作为准在本视频中，我们将比较 Go 和 Java。我们将基于 Golang 的 Fiber 框架和 Java 的 Spring Boot 创建几个简单的应用…...

编程日记 2025/6/29 10:43:43

【Spring】单例作用域下多次访问同一个接口

在Spring框架中，Controller和Service的Bean默认都是单例（Singleton）的。在多个请求同时访问Controller时，Service的Bean调用情况如下： 1. 核心机制单例Bean：Spring容器为每个Bean定义（如Serv…...

编程日记 2025/6/29 9:37:10

数据库介绍

1、什么是数据库数据库是一个“广义的概念" 1. 表示一门学科 2. 表示一类软件，管理数据的软件 3. 表示某一个具体的数据库软件 4. 表示部署了某个数据库软件的主机(电脑) 本专栏介绍的是具体的数据库软件：MySQL 数据库软件的主要功能是对数据的增删…...

编程日记 2025/6/29 12:18:02

Spring XML 配置

Spring XML 配置是 Spring Framework 的传统配置方式，通过 XML 文件定义 Bean、依赖注入、AOP 等核心功能。以下是详细的 Spring XML 配置解析： 一、基础配置 1. XML 配置文件结构 <?xml version"1.0" encoding"UTF-8"?> …...

编程日记 2025/6/29 9:37:20

AI数字人：品牌营销的新宠与增长密码（6/10）

摘要：AI数字人凭借低成本、高可控性与强互动性等优势，正成为品牌营销新宠。通过技术驱动，AI数字人从虚拟形象发展为智能交互的数字化身，广泛应用于直播、客服、内容生产等营销场景，助力品牌提升营销效果与用户互动体验…...

编程日记 2025/6/29 9:52:49

CentOS笔记本合上盖子不休眠

通过修改 /etc/systemd/logind.conf 文件中的 HandleLidSwitch 和 HandleLidSwitchDocked 设置为 ignore，可以实现合上笔记本盖子时不休眠的效果。如果有其他电源管理工具或桌面环境的设置干扰，也需要一并调整。 // 切换到root用户 su root// logind.co…...

编程日记 2025/7/19 15:57:23

Vue.js 之 `v-for` 命令详解

Vue.js 之 v-for 命令详解在 Vue.js 中，v-for 是一个非常强大的指令，用于遍历数组或对象中的数据，并渲染相应的 DOM 元素。无论是在列表展示、表单生成还是动态组件加载中，v-for 都发挥着重要作用。本文将详细介绍 v-for 的用法…...

编程日记 2025/6/29 9:37:12

Linux命令-pidstat

pidstat命令是一个用于监控系统中各个进程活动的性能监控工具。它能够实时输出每个进程的 CPU、内存、I/O 等关键性能指标。以下是关于 pidstat 命令的详细介绍： 语法 pidstat [选项] [时间间隔] [次数]常用选项 -h 或 --help ：显示帮助信息。 -v &…...

编程日记 2025/6/29 9:37:14

map和set

1.序列式容器和关联式容器在认识map和set之前，关于容器，有两个重要的分类序列式容器关联式容器序列式容器：按照元素插入的顺序保存数据，关注元素的顺序和位置，因为逻辑结构为线性序列的数据结构，两个位…...

编程日记 2025/6/29 10:55:40

CentOS 6.9 安装 Zabbix 3.0 详细教程

一、引言在 Linux 环境下，有许多实用的系统监控软件，如 Nagios、Cacti、Zabbix、Monit等。这些开源软件能帮助我们更好地管理机器，及时发现问题并警告系统维护人员。今天我们将重点研究 Zabbix，使用它的目的是为了更好地监控MySQ…...

编程日记 2025/6/29 9:37:25

通俗的理解TCP的三次握手四次挥手

前言本文是博主根据自身理解，尽量用最通俗的形式解释TCP的三次握手四次挥手。一、三次握手：为什么不是两次或四次？ 1. 三次握手过程 SYN：客户端发送SYN1, seqx（我要连接）SYNACK：服务器回复…...

编程日记 2025/6/29 12:24:44

【Python进阶】正则表达式实战指南：从基础到高阶应用

目录前言技术背景与价值当前技术痛点解决方案概述目标读者说明一、技术原理剖析核心概念图解核心作用讲解关键技术模块说明技术选型对比二、实战演示环境配置要求核心代码实现案例1：邮箱格式验证案例2：提取电话号码案例3：替换敏感信息运行…...

编程日记 2025/6/29 9:38:00

linux下内存地址数学运算

如下代码计算地址并16字节对齐： char* buffer (char*)malloc(a3 0x1000);unsigned long long tmp (((unsigned long long)buffer 0x10) & 0xffffffffffffff00);char* buf (char*)tmp;假如把地址当作整数，加减程序运算，直接转换是不行…...

编程日记 2025/6/29 9:37:52

考研单词笔记 2025.04.22

abuse v/n滥用，妄用，虐待，伤害 adopt v采用，采纳，收养，领养，正式通过，批准 apply v应用，运用，申请，适用，有效 deploy v有效利用&am…...

编程日记 2025/6/29 9:38:20

JVM虚拟机-类加载器、双亲委派模型、类装载的执行过程

一、什么是类加载器，类加载器有哪些我们目前要讲的就是类加载子系统，主要作用是将java源码编译为class字节码文件后装载到运行时数据区，运行时数据区就可以去分配内存再通过执行引擎来执行java代码。启动类加载器(也称引导类加载器)&…...

编程日记 2025/6/29 10:32:46

神经网络的 “成长密码”：正向传播与反向传播深度解析（四）

引言在神经网络的神秘世界里，正向传播和反向传播是驱动模型学习和进化的核心机制。它们如同神经网络的 “左右脑”，正向传播负责信息的前向流动与初步处理，反向传播则通过优化权重参数来提升模型性能，二者相辅相成，共…...

编程日记 2025/6/29 9:38:10

激活函数：神经网络的 “魔法开关”，开启智能之门（三）

引言在神经网络的复杂架构中，激活函数扮演着至关重要的角色，堪称神经网络的 “魔法开关”。它赋予了神经网络强大的能力，让其能够处理各种复杂的任务。本文将深入剖析激活函数的重要性、引入原因、常见类型以及选择策略，并针对面…...

编程日记 2025/6/29 9:46:53

服装印花/印烫环节计算机视觉应用设计方案

服装印花/印烫环节计算机视觉应用设计方案一、引言随着消费者对服装个性化、多样化需求的增加，服装印花/印烫环节作为服装生产中的重要一环，其质量和效率直接影响到产品的竞争力和市场占有率。传统的服装印花/印烫环节存在以下痛点： 人为…...

编程日记 2025/6/29 10:43:09

vue3:十一、主页面布局(修改左侧导航条的样式)

一、样式 1、初始样式 2、左侧导航栏搭建完成样式二、实现 1、设置左侧导航栏底色 (1)去掉顶部和左侧导航栏的底色初始页面效果顶部与左侧底色样式将代码中与顶部与左侧的样式删掉移除后页面效果加入设定背景色 #f4f6f9 加入底色后颜色展示 (2)去除菜单项底色初…...

编程日记 2025/6/29 10:05:53

Sentinel源码—8.限流算法和设计模式总结二

大纲 1.关于限流的概述 2.高并发下的四大限流算法原理及实现 3.Sentinel使用的设计模式总结 3.Sentinel使用的设计模式总结 (1)责任链模式 (2)监听器模式 (3)适配器模式 (4)模版方法模式 (5)策略模式 (6)观察者模式 (1)责任链模式一.责任链接口ProcessorSlot 二.责…...

编程日记 2025/6/29 9:38:11

Docker 部署 MySQL 数据库

Docker 部署 MySQL 数据库基于 Docker 部署 MySQL 数据库一、拉取 MySQL 镜像二、运行 MySQL 容器三、运行命令参数详解四、查看容器运行状态基于 Docker 部署 MySQL 数据库一、拉取 MySQL 镜像在开始之前，请确保你的 Docker 环境已经正确安装并可以正常运行。…...

编程日记 2025/6/29 12:04:15

【Linux运维涉及的基础命令与排查方法大全】

文章目录前言1、计算机网络常用端口2、Kali Linux中常用的命令3、Kali Linux工具的介绍4、Ubuntu没有网络连接解决方法5、获取路由6、数据库端口前言以下介绍计算机常见的端口已经对应的网络协议，Linux中常用命令，以及平时运维中使用的排查网络故障的…...

编程日记 2025/6/29 10:06:57

映射（Mapping）和地址（Address）

Addresses （地址） 以太坊区块链由 _ account _ (账户)组成，你可以把它想象成银行账户。一个帐户的余额是以太 （在以太坊区块链上使用的币种），你可以和其他帐户之间支付和接受以太币，就像你的银…...

编程日记 2025/6/29 11:21:19

用Java实现简易区块链：从零开始的探索

📢 友情提示： 本文由银河易创AI（https://ai.eaigx.com）平台gpt-4o-mini模型辅助创作完成，旨在提供灵感参考与技术分享，文中关键数据、代码与结论建议通过官方渠道验证。区块链技术作为近年来的热门话题&am…...

编程日记 2025/6/29 11:40:28

Spark-Streaming

Spark-Streaming 一、Spark-Streaming简介 1、Spark-Streaming概述 1.1、Spark-Streaming是什么 Spark Streaming 用于流式数据的处理。Spark Streaming 支持的数据输入源很多，例如：Kafka、Flume、Twitter等，以及和简单的 TCP 套接字等等…...

编程日记 2025/6/29 9:40:45

工程投标k值分析系统（基于微服务实现）

1 需求总括 2 企业管理模块：新增、删除、修改企业/部门 <...

编程日记 2025/6/29 12:16:31

一、STL 算法

二、STL 算法分类

三、STL 排序算法

（1） sort

（2） stable_sort

（3）partial_sort

（4）nth_element

（5）reverse

相关文章：

（1） `sort`

（2） `stable_sort`

（3）`partial_sort`

（4）`nth_element`

（5）`reverse`