计算机软考中级 知识点记忆——排序算法 冒泡排序-插入排序- 归并排序等 各种排序算法知识点整理
一、📌 分类与比较
排序算法 | 最优时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 应用场景与特点 | 算法策略 |
冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 简单易实现,适用于小规模数据排序。 | 交换排序策略 |
插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 数据量小或基本有序时高效。 | 关键字:基本有序 |
选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 简单但效率低,适用于小规模数据。 | |
快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 | 最常用的排序算法,适用于大规模数据。 | 分治法 关键字:有序或者逆序 |
归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 外部排序的最佳选择。 | 分治法 |
堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 适用于堆结构、优先队列的实现。 | |
希尔排序 | O(n log n)~O(n²) | O(n log n) | O(n²) | O(1) | 不稳定 | 改进的插入排序,适用于中规模数据。 | |
基数排序 | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | 稳定 | 适用于整数排序、字符串排序。 | |
计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 稳定 | 适用于范围较小的整数排序。 | |
桶排序 | O(n) | O(n) | O(n²) | O(n + k) | 稳定 | 适用于均匀分布的数据。 |
📌 1. 基本排序算法(简单易实现)
- 冒泡排序、插入排序、选择排序
- 时间复杂度高,但易于实现和理解。
- 常用于小规模数据或已基本有序的场景。
- 平均时间和最坏时间T复杂度为:O(n^2)
- 最好的时间T复杂度为:O(n) 选择最好依旧是O(n^2)
- 也就是在基本排序算法中选择的时间不管好坏都是O(n^2)
📌 2. 高效排序算法(分治思想、树结构)
- 快速排序、归并排序、堆排序、希尔排序
- 基于分治思想(快速排序、归并排序)或堆结构(堆排序)。
- 适用于大规模数据排序。
- 平均时间T复杂度为:O(n log n)
- 最坏时间T复杂度为:快速、希尔是O(n^2) ,其余不变
- 最好时间T复杂度为:O(n log n) 和平均一样,除了希尔是O(n log n) ~O(n^2)
📌 3. 非比较排序算法(适用于特定场景)
- 基数排序、计数排序、桶排序
- 不依赖于比较操作,适用于整数或特定场景的数据排序。
- 时间复杂度与输入数据特性有关。
单独的记忆点 空间复杂度:
高级排序的快速排序空间复杂度是:O(log n)
高级排序的归并排序和非比较排序算法的空间复杂度是:O(n)
其余的都是O(1) 原地排序
空间复杂度越大,说明使用的额外空间更多。
📌 4. 常考点与总结
📚 软考中常考内容:
- 各种排序算法的 时间复杂度、空间复杂度、稳定性分析。
- 适用场景:如什么时候选择快速排序、什么时候使用归并排序。
- 基于 分治思想(快速排序、归并排序)与堆结构(堆排序) 的应用。
- 非比较排序的特点与应用(基数排序、计数排序、桶排序)。
💡 记忆技巧:
- 稳定性:一般来说,非比较排序和插入、冒泡、归并是稳定的。(非比较排序 + 茶树泡饼)树:基数排序
- 时间复杂度 O(n log n):快速排序、归并排序、堆排序。
- 非比较排序:计数、基数、桶排序特别适用于整数或特定场景。
效率排序来看:
- O(1) > O(log n) > O(n) > O(n log n) > O(n²) > O(2ⁿ) > O(n!)
- 你的理解非常准确!我们通常把
O(n log n)
算法称为 “高级排序算法”,而把O(n²)
算法称为 “基础排序算法”。
二、时间复杂度的描述,自简单到复杂
1. O(1) - 常数时间复杂度。无论输入多大,执行时间都是固定的。
2. O(log n) - 对数时间复杂度。随着输入规模的增大,所需时间按对数级别增长。
3. O(n) - 线性时间复杂度。执行时间直接与输入规模成正比。
4. O(n^2) - 平方时间复杂度。执行时间为输入规模的平方。
5. O(2^n) - 指数时间复杂度。随着输入规模的增大,所需时间呈指数级增长。
6. O(n!) - 阶乘时间复杂度。这是非常高的一种复杂度形式,不适用于大多数实际应用场景。
相关文章:
计算机软考中级 知识点记忆——排序算法 冒泡排序-插入排序- 归并排序等 各种排序算法知识点整理
一、📌 分类与比较 排序算法 最优时间复杂度 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性 应用场景与特点 算法策略 冒泡排序 O(n) O(n) O(n) O(1) 稳定 简单易实现,适用于小规模数据排序。 交换排序策略 插入排序 O(n) O(n) O…...
STC32G12K128单片机GPIO模式SPI操作NorFlash并实现FatFS文件系统
STC32G12K128单片机GPIO模式SPI操作NorFlash并实现FatFS文件系统 Norflash简介NorFlash操作驱动代码文件系统测试代码 Norflash简介 NOR Flash是一种类型的非易失性存储器,它允许在不移除电源的情况下保留数据。NOR Flash的名字来源于其内部结构中使用的NOR逻辑门。…...
uniapp-x 二维码生成
支持X,二维码生成,支持微信小程序,android,ios,网页 - DCloud 插件市场 免费的单纯用爱发电的...
当HTTP遇到SQL注入:Java开发者的攻防实战手册
一、从HTTP请求到数据库查询:漏洞如何产生? 危险的参数拼接:Servlet中的经典错误 漏洞代码重现: public void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {String category = request.getParameter("…...
[dp20_完全背包] 介绍 | 零钱兑换
目录 1. 完全背包 题解 背包必须装满 2.零钱兑换 题解 1. 完全背包 链接: DP42 【模板】完全背包 描述 你有一个背包,最多能容纳的体积是V。 现在有n种物品,每种物品有任意多个,第i种物品的体积为vivi ,价值为wiwi。 &a…...
精打细算 - GPU 监控
精打细算 - GPU 监控 在上一篇,咱们历经千辛万苦,终于让应用程序在 Pod 的“驾驶舱”里成功地“点火”并用上了 GPU。太棒了!但是,车开起来是一回事,知道车速多少、油耗多少、引擎水温是否正常,则是另一回事,而且同样重要,对吧? 我们的 GPU 应用跑起来了,但新的问题…...
故障诊断 | CNN-BiGRU-Attention故障诊断
效果一览 摘要 在现代工业生产中,设备的稳定运行至关重要,故障诊断作为保障设备安全、高效运行的关键技术,其准确性和及时性直接影响着生产效率与成本[[doc_refer_1]][[doc_refer_2]]。随着工业设备复杂性的不断增加,传统故障诊断方法已难以满足实际需求。深度学习技术凭借…...
单片机AIN0、AIN1引脚功能
目录 1. 模拟-数字转换器(ADC) 2. 交流电源(AC) 总结 这两部分有什么区别? 在这个电路图中,两个部分分别是模拟-数字转换器(ADC)和交流电源(AC)。以下是这…...
交换机与路由器的主要区别:深入分析其工作原理与应用场景
在现代网络架构中,交换机和路由器是两种至关重要的设备。它们在网络中扮演着不同的角色,但很多人对它们的工作原理和功能特性并不十分清楚。本文将深入分析交换机与路由器的主要区别,并探讨它们的工作原理和应用场景。 一、基本定义 1. 交换…...
uniApp小程序保存定制二维码到本地(V3)
这里的二维码组件用的 uv-ui 的二维码 可以按需引入 QRCode 二维码 | 我的资料管理-uv-ui 是全面兼容vue32、nvue、app、h5、小程序等多端的uni-app生态框架 <uv-qrcode ref"qrcode" :size"280" :value"payCodeUrl"></uv-qrcode>&l…...
手机投屏到电视方法
一、投屏软件 比如乐播投屏 二、视频软件 腾讯视频、爱奇艺 三、手机无线投屏功能 四、有线投屏 五、投屏器...
桌面应用UI开发方案
一、基于 Web 技术的跨平台方案 Electron Python/Go 特点: 技术栈:前端使用 HTML/CSS/JS,后端通过 Node.js 集成 Python/Go 模块或服务。 跨平台:支持 Windows、macOS、Linux 桌面端,适合开发桌面应用。 生态成熟&…...
FFmpeg+Nginx+VLC打造M3U8直播
一、视频直播的技术原理和架构方案 直播模型一般包括三个模块:主播方、服务器端和播放端 主播放创造视频,加美颜、水印、特效、采集后推送给直播服务器 播放端: 直播服务器端:收集主播端的视频推流,将其放大后推送给…...
山东科技大学深度学习考试回忆
目录 一、填空(五个空,十分) 二、选择题(五个,十分) 三、判断题(五个,五分) 四、论述题(四个,四十分) 五、计算题(二个ÿ…...
【Flutter动画深度解析】性能与美学的完美平衡之道
Flutter的动画系统是其UI框架中最引人注目的部分之一,它既能创造令人惊艳的视觉效果,又需要开发者对性能有深刻理解。本文将深入剖析Flutter动画的实现原理、性能优化策略以及设计美学,帮助你打造既流畅又美观的用户体验。 一、Flutter动画核…...
【嵌入式】——Linux系统远程操作和程序编译
目录 一、虚拟机配置网络设置 二、使用PuTTY登录新建的账户 1、在ubuntu下开启ssh服务 2、使用PuTTY连接 三、树莓派实现远程登录 四、树莓派使用VNC viewer登录 五、Linux使用talk聊天程序 1、使用linux自带的talk命令 2、使用c语言编写一个talk程序 一、虚拟机配置网络…...
零、HarmonyOS应用开发者基础学习总览
零、HarmonyOS应用开发者基础认证 1 整体学习内容概览 1 整体学习内容概览 通过系统化的课程学习,熟练掌握 DevEco Studio,ArkTS,ArkUI,预览器,模拟器,SDK 等 HarmonyOS 应用开发的关键概念,具…...
记录一次项目中使用pdf预览过程以及遇到问题以及如何解决
背景 项目中现有的pdf浏览解析不能正确解析展示一些pdf文件,要么内容一直在加载中展示不出来,要么展示的格式很凌乱 解决 方式一:(优点:比较无脑,缺点:不能解决遇到的一些特殊问题࿰…...
致远OA——自定义开发rest接口
文章目录 :apple: 业务流程 🍎 业务流程 代码案例: https://pan.quark.cn/s/57fa808c823f 官方文档: https://open.seeyoncloud.com/seeyonapi/781/https://open.seeyoncloud.com/v5devCTP/39/783.html 登录系统 —— 后台管理 —— 切换系…...
STL之vector基本操作
写在前面 我使用的编译器版本是 g 11.4.0 (Ubuntu 22.04 默认版本),支持C17的全部特性,支持C20的部分特性。 vector的作用 我们知道vector是动态数组(同时在堆上存储数组元素),我们在不确定数…...
dac直通线还是aoc直通线? sfp使用
"DAC直通线" 和 "AOC直通线" 都是高速互连线缆,用于数据中心、服务器、交换机等设备之间的高速互连。它们的选择主要取决于以下几个方面: 🔌 DAC(Direct Attach Cable,直连铜缆) 材质&…...
【Linux篇】探索进程间通信:如何使用匿名管道构建高效的进程池
从零开始:通过匿名管道实现进程池的基本原理 一. 进程间通信1.1 基本概念1.2 通信目的1.3 通信种类1.3.1 同步通信1.3.2 异步通信 1.4 如何通信 二. 管道2.1 什么是管道2.2 匿名管道2.2.1 pipe()2.2.2 示例代码:使用 pipe() 进行父子进程通信2.2.3 管道容…...
Mixture-of-Experts with Expert Choice Routing:专家混合模型与专家选择路由
摘要 稀疏激活的专家混合模型(MoE)允许在保持每个token或每个样本计算量不变的情况下,大幅增加参数数量。然而,糟糕的专家路由策略可能导致某些专家未被充分训练,从而使得专家在特定任务上过度或不足专业化。先前的研究通过使用top-k函数为每个token分配固定数量的专家,…...
ai学习中收藏网址【1】
https://github.com/xuwenhao/geektime-ai-course课程⾥所有的代码部分,通过 Jupyter Notebook 的形式放在了 GitHub 上 https://github.com/xuwenhao/geektime-ai-course 图片创作 https://www.midjourney.com/explore?tabtop 创建填⾊本 How to Create Midjour…...
【滑动窗口】最⼤连续 1 的个数 III(medium)
⼤连续 1 的个数 III(medium) 题⽬描述:解法(滑动窗⼝):算法思路:算法流程: C 算法代码:Java 算法代码: 题⽬链接:1004. 最⼤连续 1 的个数 III …...
ClawCloud的免费空间(github用户登录可以获得$5元/月的免费额度)
免费的空间 Welcome to ClawCloud Lets create your workspace 官网:ClawCloud | Cloud Infrastructure And Platform for Developers 区域选择新加坡 然后这个页面会变成新加坡区域,再按一次确定,就创建好了工作台。 初始界面࿰…...
sql之DML(insert、delete、truncate、update、replace))
🎯 本文专栏:MySQL深入浅出 🚀 作者主页:小度爱学习 数据库使用时,大多数情况下,开发者只会操作数据,也是就增删改查(CRUD)。 增删改查四条语句,最重要的是查…...
Spring Boot常用注解全解析:从入门到实战
🌱 Spring Boot常用注解全解析:从入门到实战 #SpringBoot核心 #注解详解 #开发技巧 #高效编程 一、核心启动与配置注解 1. SpringBootApplication 作用:标记主启动类,整合了Configuration、EnableAutoConfiguration和Component…...
Python 赋能区块链教育:打造去中心化学习平台
Python 赋能区块链教育:打造去中心化学习平台 引言 区块链技术正在重塑全球多个行业,而教育领域也不例外。传统的在线学习平台往往依赖中心化存储和管理模式,导致数据安全、用户隐私、资源共享等问题难以解决。而随着 Web 3.0 的发展,区块链在教育场景中的应用逐渐受到关…...
verilog float mult
module pipe_float_mul(input wire clk ,// 时钟信号input wire en ,// 使能信号input wire rst_n ,// 复位信号input wire round_cfg ,// 决…...
Android开发四大组件和生命周期及setFlags
文章目录 Android开发四大组件1. Activity(活动)2. Service(服务)3. BroadcastReceiver(广播接收器)4. ContentProvider(内容提供者)共同特点 Activity 生命周期详解完整的生命周期方…...
mysql的函数(第二期)
九、窗口函数(MySQL 8.0) 适用于对结果集的子集(窗口)进行计算,常用于数据分析场景。 ROW_NUMBER() 作用:为每一行生成唯一的序号。示例:按分数降序排名 SELECT n…...
MATLAB 控制系统设计与仿真 - 39
多变量系统控制器设计实例2 假如原系统对象中有位于虚轴上的极点,则不能直接应用鲁棒控制设计来设计控制器。 在这样的情况下,需引入一个新的变量p,使得 即可在对象模型中用p变量取代s变量,这样的变换称为双线性变换,…...
深入理解C++ 中的vector容器
一、引言 在C 的标准模板库(STL)中, vector 是一个极为常用且功能强大的序列容器。它就像是一个动态数组,既能享受数组随机访问元素的高效性,又能灵活地动态调整大小。在本文中,我们将深入探讨 vector …...
ESP-ADF外设子系统深度解析:esp_peripherals组件架构与核心设计(显示输出类外设之LED)
目录 ESP-ADF外设子系统深度解析:esp_peripherals组件架构与核心设计(显示输出类外设之LED)简介模块概述功能定义架构位置核心特性 LED外设分析LED外设概述LED外设功能特点常见应用场景LED外设架构图 LED外设API和数据结构公共API事件类型配置…...
[特殊字符] Kotlin与C的类型别名终极对决:typealias vs typedef,如何让代码脱胎换骨?
在 Kotlin 中,typealias 是一个非常实用的关键字,它可以为已有的类型定义一个新的名称,起到简化代码和提升可读性的作用。比如: // 定义一个复杂函数类型的别名 typealias ClickListener (View, Int) -> Unitfun setOnClickL…...
第9期:文本条件生成(CLIP + Diffusion)详解
“让我们用一句话,让模型画出一幅画。” 在前几期中我们学习了 Denoising Diffusion Probabilistic Models(DDPM)如何在无条件情况下生成图像。而在本期,我们将跨入更具挑战性但也更酷的领域 —— 文本条件图像生成(Te…...
8 编程笔记全攻略:Markdown 语法精讲、Typora 编辑器全指南(含安装激活、基础配置、快捷键详解、使用技巧)
1 妙笔在手,编程无忧! 1.1 编程为啥要做笔记?这答案绝了! 嘿,各位键盘魔法师!学编程不记笔记,就像吃火锅不配冰可乐 —— 爽到一半直接噎住!你以为自己脑子是顶配 SSD,结…...
C#测试linq中的左连接的基本用法
使用linq联表或者连接两个对象集合查询时一般使用的是join关键字,返回结果中包含两个表或两个对象集合中连接字段相等的数据记录,如果要实现sql语句中的左连接效果,并没有现成的left join关键字,此时可以使用DefaultIfEmpty 实现左…...
【Android面试八股文】Android系统架构【一】
Android系统架构图 1.1 安卓系统启动 1.设备加电后执行第一段代码:Bootloader 系统引导分三种模式:fastboot,recovery,normal: fastboot模式:用于工厂模式的刷机。在关机状态下,按返回开机 键进…...
什么是 Stream
Stream 是对集合对象功能的增强,它不是集合,也不存储数据,而是从集合中抽象出一条数据通道,让你可以用链式方式一步步处理数据。 🔧 常见操作分类 类型方法举例创建stream(), Stream.of(), Arrays.stream()中间操作fi…...
网络编程 - 4 ( TCP )
目录 TCP 流套接字编程 API 介绍 SeverSocket Socket 用 TCP 实现一个回显服务器 服务端 客户端 运行调试 第一个问题:PrintWriter 内置的缓冲区 - flush 刷新解决 第二个问题:上述代码中,需要进行 close 操作吗? 第三…...
在STM32的定时器外设中,选择使用哪个外部时钟配置函数
在STM32的定时器外设中,选择使用哪个外部时钟配置函数主要取决于以下几个因素: 时钟源类型: TIM_ITRxExternalClockConfig:使用内部触发输入(ITRx),即来自其他定时器的时钟信号 TIM_TIxExternalClockConfig࿱…...
【Tauri2】026——Tauri+Webassembly
前言 不多废话 直言的说,笔者看到这篇文章大佬的文章 【04】Tauri 入门篇 - 集成 WebAssembly - 知乎https://zhuanlan.zhihu.com/p/533025312尝试集成一下WebAssembly,直接开始 正文 准备工作 新建一个项目 安装 vite的rsw插件和rsw pnpm instal…...
jenkins尾随命令
在访问jenkins的网址后面可以追加命令,比如访问地址是 http://10.20.0.124:8080/,常用的有以下几种方式: 1.关闭Jenkins 只要浏览器输入http://10.20.0.124:8080/exit即可退出,或者http://localhost:8080/exit 2.重启Jenkins …...
基于机器学习 LSTM 算法的豆瓣评论情感分析系统
基于机器学习 LSTM 算法的豆瓣评论情感分析系统 博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 ὄ…...
腾讯云对象存储m3u8文件使用腾讯播放器播放
参考腾讯云官方文档: 播放器 SDK Demo 体验_腾讯云 重要的一步来了: 登录腾讯云控制台,找到对象存储的存储桶。 此时,再去刷新刚才创建的播放器html文件,即可看到播放画面了。...
基于chatgpt和deepseek解答显卡的回答
当然可以!了解显卡特别是英伟达(NVIDIA)的系列,对于选购、升级或者了解游戏和创作性能都很重要。下面我帮你系统整理一下 NVIDIA 显卡的各个系列,并加点选购建议,方便你快速上手。 chatgpt 🧠 …...
2025年渗透测试面试题总结-拷打题库06(题目+回答)
网络安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 1. Sleep被禁用后的SQL注入 2. XSS属性控制利用 3. CSRF防护 4. 危险请求头 5. XXE高发场景 6. Ja…...
【一起学Rust】使用Thunk工具链实现Rust应用对Windows XP/7的兼容性适配实战
前言 在Rust语言快速发展的今天,开发者经常面临将现代语言特性与遗留系统兼容的挑战。特别是在工业控制、嵌入式设备等场景中,Windows XP/7等经典操作系统仍占据重要地位。本文深入解析如何通过Thunk工具链突破Rust编译器对旧版Windows系统的兼容性限制…...