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

计算机软考中级 知识点记忆——排序算法 冒泡排序-插入排序- 归并排序等 各种排序算法知识点整理

一、📌 分类与比较

排序算法

最优时间复杂度

平均时间复杂度

最坏时间复杂度

空间复杂度

稳定性

应用场景与特点

算法策略

冒泡排序

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. 常考点与总结

📚 软考中常考内容:

  1. 各种排序算法的 时间复杂度、空间复杂度、稳定性分析
  2. 适用场景:如什么时候选择快速排序、什么时候使用归并排序。
  3. 基于 分治思想(快速排序、归并排序)与堆结构(堆排序) 的应用。
  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 特点&#xff1a; 技术栈&#xff1a;前端使用 HTML/CSS/JS&#xff0c;后端通过 Node.js 集成 Python/Go 模块或服务。 跨平台&#xff1a;支持 Windows、macOS、Linux 桌面端&#xff0c;适合开发桌面应用。 生态成熟&…...

FFmpeg+Nginx+VLC打造M3U8直播

一、视频直播的技术原理和架构方案 直播模型一般包括三个模块&#xff1a;主播方、服务器端和播放端 主播放创造视频&#xff0c;加美颜、水印、特效、采集后推送给直播服务器 播放端&#xff1a; 直播服务器端&#xff1a;收集主播端的视频推流&#xff0c;将其放大后推送给…...

山东科技大学深度学习考试回忆

目录 一、填空&#xff08;五个空&#xff0c;十分&#xff09; 二、选择题(五个&#xff0c;十分&#xff09; 三、判断题&#xff08;五个&#xff0c;五分&#xff09; 四、论述题&#xff08;四个&#xff0c;四十分&#xff09; 五、计算题&#xff08;二个&#xff…...

【Flutter动画深度解析】性能与美学的完美平衡之道

Flutter的动画系统是其UI框架中最引人注目的部分之一&#xff0c;它既能创造令人惊艳的视觉效果&#xff0c;又需要开发者对性能有深刻理解。本文将深入剖析Flutter动画的实现原理、性能优化策略以及设计美学&#xff0c;帮助你打造既流畅又美观的用户体验。 一、Flutter动画核…...

【嵌入式】——Linux系统远程操作和程序编译

目录 一、虚拟机配置网络设置 二、使用PuTTY登录新建的账户 1、在ubuntu下开启ssh服务 2、使用PuTTY连接 三、树莓派实现远程登录 四、树莓派使用VNC viewer登录 五、Linux使用talk聊天程序 1、使用linux自带的talk命令 2、使用c语言编写一个talk程序 一、虚拟机配置网络…...

零、HarmonyOS应用开发者基础学习总览

零、HarmonyOS应用开发者基础认证 1 整体学习内容概览 1 整体学习内容概览 通过系统化的课程学习&#xff0c;熟练掌握 DevEco Studio&#xff0c;ArkTS&#xff0c;ArkUI&#xff0c;预览器&#xff0c;模拟器&#xff0c;SDK 等 HarmonyOS 应用开发的关键概念&#xff0c;具…...

记录一次项目中使用pdf预览过程以及遇到问题以及如何解决

背景 项目中现有的pdf浏览解析不能正确解析展示一些pdf文件&#xff0c;要么内容一直在加载中展示不出来&#xff0c;要么展示的格式很凌乱 解决 方式一&#xff1a;&#xff08;优点&#xff1a;比较无脑&#xff0c;缺点&#xff1a;不能解决遇到的一些特殊问题&#xff0…...

致远OA——自定义开发rest接口

文章目录 :apple: 业务流程 &#x1f34e; 业务流程 代码案例&#xff1a; https://pan.quark.cn/s/57fa808c823f 官方文档&#xff1a; https://open.seeyoncloud.com/seeyonapi/781/https://open.seeyoncloud.com/v5devCTP/39/783.html 登录系统 —— 后台管理 —— 切换系…...

STL之vector基本操作

写在前面 我使用的编译器版本是 g 11.4.0 &#xff08;Ubuntu 22.04 默认版本&#xff09;&#xff0c;支持C17的全部特性&#xff0c;支持C20的部分特性。 vector的作用 我们知道vector是动态数组&#xff08;同时在堆上存储数组元素&#xff09;&#xff0c;我们在不确定数…...

dac直通线还是aoc直通线? sfp使用

"DAC直通线" 和 "AOC直通线" 都是高速互连线缆&#xff0c;用于数据中心、服务器、交换机等设备之间的高速互连。它们的选择主要取决于以下几个方面&#xff1a; &#x1f50c; DAC&#xff08;Direct Attach Cable&#xff0c;直连铜缆&#xff09; 材质&…...

【Linux篇】探索进程间通信:如何使用匿名管道构建高效的进程池

从零开始&#xff1a;通过匿名管道实现进程池的基本原理 一. 进程间通信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 示例代码&#xff1a;使用 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课程⾥所有的代码部分&#xff0c;通过 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&#xff08;medium&#xff09; 题⽬描述&#xff1a;解法&#xff08;滑动窗⼝&#xff09;&#xff1a;算法思路&#xff1a;算法流程&#xff1a; C 算法代码&#xff1a;Java 算法代码&#xff1a; 题⽬链接&#xff1a;1004. 最⼤连续 1 的个数 III …...

ClawCloud的免费空间(github用户登录可以获得$5元/月的免费额度)

免费的空间 Welcome to ClawCloud Lets create your workspace 官网&#xff1a;ClawCloud | Cloud Infrastructure And Platform for Developers 区域选择新加坡 然后这个页面会变成新加坡区域&#xff0c;再按一次确定&#xff0c;就创建好了工作台。 初始界面&#xff0…...

sql之DML(insert、delete、truncate、update、replace))

&#x1f3af; 本文专栏&#xff1a;MySQL深入浅出 &#x1f680; 作者主页&#xff1a;小度爱学习 数据库使用时&#xff0c;大多数情况下&#xff0c;开发者只会操作数据&#xff0c;也是就增删改查&#xff08;CRUD&#xff09;。 增删改查四条语句&#xff0c;最重要的是查…...

Spring Boot常用注解全解析:从入门到实战

&#x1f331; Spring Boot常用注解全解析&#xff1a;从入门到实战 #SpringBoot核心 #注解详解 #开发技巧 #高效编程 一、核心启动与配置注解 1. SpringBootApplication 作用&#xff1a;标记主启动类&#xff0c;整合了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&#xff08;活动&#xff09;2. Service&#xff08;服务&#xff09;3. BroadcastReceiver&#xff08;广播接收器&#xff09;4. ContentProvider&#xff08;内容提供者&#xff09;共同特点 Activity 生命周期详解完整的生命周期方…...

mysql的函数(第二期)

九、窗口函数&#xff08;MySQL 8.0&#xff09;​​ 适用于对结果集的子集&#xff08;窗口&#xff09;进行计算&#xff0c;常用于数据分析场景。 ​​ROW_NUMBER()​​ ​​作用​​&#xff1a;为每一行生成唯一的序号。​​示例​​&#xff1a;按分数降序排名 SELECT n…...

MATLAB 控制系统设计与仿真 - 39

多变量系统控制器设计实例2 假如原系统对象中有位于虚轴上的极点&#xff0c;则不能直接应用鲁棒控制设计来设计控制器。 在这样的情况下&#xff0c;需引入一个新的变量p&#xff0c;使得 即可在对象模型中用p变量取代s变量&#xff0c;这样的变换称为双线性变换&#xff0c…...

深入理解C++ 中的vector容器

一、引言 在C 的标准模板库&#xff08;STL&#xff09;中&#xff0c; vector 是一个极为常用且功能强大的序列容器。它就像是一个动态数组&#xff0c;既能享受数组随机访问元素的高效性&#xff0c;又能灵活地动态调整大小。在本文中&#xff0c;我们将深入探讨 vector …...

ESP-ADF外设子系统深度解析:esp_peripherals组件架构与核心设计(显示输出类外设之LED)

目录 ESP-ADF外设子系统深度解析&#xff1a;esp_peripherals组件架构与核心设计&#xff08;显示输出类外设之LED&#xff09;简介模块概述功能定义架构位置核心特性 LED外设分析LED外设概述LED外设功能特点常见应用场景LED外设架构图 LED外设API和数据结构公共API事件类型配置…...

[特殊字符] Kotlin与C的类型别名终极对决:typealias vs typedef,如何让代码脱胎换骨?

在 Kotlin 中&#xff0c;typealias 是一个非常实用的关键字&#xff0c;它可以为已有的类型定义一个新的名称&#xff0c;起到简化代码和提升可读性的作用。比如&#xff1a; // 定义一个复杂函数类型的别名 typealias ClickListener (View, Int) -> Unitfun setOnClickL…...

第9期:文本条件生成(CLIP + Diffusion)详解

“让我们用一句话&#xff0c;让模型画出一幅画。” 在前几期中我们学习了 Denoising Diffusion Probabilistic Models&#xff08;DDPM&#xff09;如何在无条件情况下生成图像。而在本期&#xff0c;我们将跨入更具挑战性但也更酷的领域 —— 文本条件图像生成&#xff08;Te…...

8 编程笔记全攻略:Markdown 语法精讲、Typora 编辑器全指南(含安装激活、基础配置、快捷键详解、使用技巧)

1 妙笔在手&#xff0c;编程无忧&#xff01; 1.1 编程为啥要做笔记&#xff1f;这答案绝了&#xff01; 嘿&#xff0c;各位键盘魔法师&#xff01;学编程不记笔记&#xff0c;就像吃火锅不配冰可乐 —— 爽到一半直接噎住&#xff01;你以为自己脑子是顶配 SSD&#xff0c;结…...

C#测试linq中的左连接的基本用法

使用linq联表或者连接两个对象集合查询时一般使用的是join关键字&#xff0c;返回结果中包含两个表或两个对象集合中连接字段相等的数据记录&#xff0c;如果要实现sql语句中的左连接效果&#xff0c;并没有现成的left join关键字&#xff0c;此时可以使用DefaultIfEmpty 实现左…...

【Android面试八股文】Android系统架构【一】

Android系统架构图 1.1 安卓系统启动 1.设备加电后执行第一段代码&#xff1a;Bootloader 系统引导分三种模式&#xff1a;fastboot&#xff0c;recovery&#xff0c;normal&#xff1a; fastboot模式&#xff1a;用于工厂模式的刷机。在关机状态下&#xff0c;按返回开机 键进…...

什么是 Stream

Stream 是对集合对象功能的增强&#xff0c;它不是集合&#xff0c;也不存储数据&#xff0c;而是从集合中抽象出一条数据通道&#xff0c;让你可以用链式方式一步步处理数据。 &#x1f527; 常见操作分类 类型方法举例创建stream(), Stream.of(), Arrays.stream()中间操作fi…...

网络编程 - 4 ( TCP )

目录 TCP 流套接字编程 API 介绍 SeverSocket Socket 用 TCP 实现一个回显服务器 服务端 客户端 运行调试 第一个问题&#xff1a;PrintWriter 内置的缓冲区 - flush 刷新解决 第二个问题&#xff1a;上述代码中&#xff0c;需要进行 close 操作吗&#xff1f; 第三…...

在STM32的定时器外设中,选择使用哪个外部时钟配置函数

在STM32的定时器外设中&#xff0c;选择使用哪个外部时钟配置函数主要取决于以下几个因素&#xff1a; 时钟源类型&#xff1a; TIM_ITRxExternalClockConfig&#xff1a;使用内部触发输入(ITRx)&#xff0c;即来自其他定时器的时钟信号 TIM_TIxExternalClockConfig&#xff1…...

【Tauri2】026——Tauri+Webassembly

前言 不多废话 直言的说&#xff0c;笔者看到这篇文章大佬的文章 【04】Tauri 入门篇 - 集成 WebAssembly - 知乎https://zhuanlan.zhihu.com/p/533025312尝试集成一下WebAssembly&#xff0c;直接开始 正文 准备工作 新建一个项目 安装 vite的rsw插件和rsw pnpm instal…...

jenkins尾随命令

在访问jenkins的网址后面可以追加命令&#xff0c;比如访问地址是 http://10.20.0.124:8080/&#xff0c;常用的有以下几种方式&#xff1a; 1.关闭Jenkins 只要浏览器输入http://10.20.0.124:8080/exit即可退出&#xff0c;或者http://localhost:8080/exit 2.重启Jenkins …...

基于机器学习 LSTM 算法的豆瓣评论情感分析系统

基于机器学习 LSTM 算法的豆瓣评论情感分析系统 博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f44…...

腾讯云对象存储m3u8文件使用腾讯播放器播放

参考腾讯云官方文档&#xff1a; 播放器 SDK Demo 体验_腾讯云 重要的一步来了&#xff1a; 登录腾讯云控制台&#xff0c;找到对象存储的存储桶。 此时&#xff0c;再去刷新刚才创建的播放器html文件&#xff0c;即可看到播放画面了。...

基于chatgpt和deepseek解答显卡的回答

当然可以&#xff01;了解显卡特别是英伟达&#xff08;NVIDIA&#xff09;的系列&#xff0c;对于选购、升级或者了解游戏和创作性能都很重要。下面我帮你系统整理一下 NVIDIA 显卡的各个系列&#xff0c;并加点选购建议&#xff0c;方便你快速上手。 chatgpt &#x1f9e0; …...

2025年渗透测试面试题总结-拷打题库06(题目+回答)

网络安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 1. Sleep被禁用后的SQL注入 2. XSS属性控制利用 3. CSRF防护 4. 危险请求头 5. XXE高发场景 6. Ja…...

【一起学Rust】使用Thunk工具链实现Rust应用对Windows XP/7的兼容性适配实战

前言 在Rust语言快速发展的今天&#xff0c;开发者经常面临将现代语言特性与遗留系统兼容的挑战。特别是在工业控制、嵌入式设备等场景中&#xff0c;Windows XP/7等经典操作系统仍占据重要地位。本文深入解析如何通过Thunk工具链突破Rust编译器对旧版Windows系统的兼容性限制…...