软设之快速排序
快速排序是冒泡排序的改进算法
它采用的是分治法,基本思想是把原问题分解为若干规模更小但结构与原问题相似的子问题,通过递归解决这些子问题,然后将这些子问题的解组合成原问题的解。
它的步骤是
1.在待排序的n个记录中任取一个记录,以该记录的排序码为准,将所有记录都分成两组,第1组都小于该数,第2组都大于该数。
2.采用相同方法对左右两组分别进行排序,直到所有记录都排到相应位置。
以数组57,68,59,52为例
选择57作为基准数组
57和52比较,52小,57和52交换位置
52,68,59,57
选择68和57比较,57小,57和68交换位置
52,57,59,68。
由于元素数量小,已经完成排序了。同样初始顺序数组,需要操作的次数比冒泡排序少多了。
快速排序的基准元素:一般是第一个元素,也可以是中位数。
快速排序是一种不稳定的排序方法,平均和最优情况下时间复杂度是O(nlog(2)n)
最差的情况,此时数组基本有序,以第一个时间复杂度是O(n^2)。以中位数为基准情况,时间复杂度是O(nlog(2)n)
空间复杂度是O(1)
需要辅助空间存储左侧数据和右侧数据,空间复杂度为O(n)
需要记录所有基准元素时,空间复杂度为O(log(2)n)
相关文章:
软设之快速排序
快速排序是冒泡排序的改进算法 它采用的是分治法,基本思想是把原问题分解为若干规模更小但结构与原问题相似的子问题,通过递归解决这些子问题,然后将这些子问题的解组合成原问题的解。 它的步骤是 1.在待排序的n个记录中任取一个记录&…...
从零学算法2965
2965. 找出缺失和重复的数字 给你一个下标从 0 开始的二维整数矩阵 grid,大小为 n * n ,其中的值在 [1, n2] 范围内。除了 a 出现 两次,b 缺失 之外,每个整数都 恰好出现一次 。 任务是找出重复的数字a 和缺失的数字 b 。 返回一个…...

【Mac版】Java生成二维码
软件版本 IntelliJ IDEA:2023.2 JDK:17 Tomcat:10.1.11 Maven:3.9.3 技术栈 servlet谷歌的:zxing 生成普通的黑白二维码在二维码中间添加一个小图标 github开源项目:qrcode qrcode开源项目的内部是基于z…...
ROS2自定义服务接口
ROS2自定义服务接口 在src/village_interface 下构建srv文件夹 src/village_interface/srv 下新建一个BorrowMoney.srv 遵循大小写编程规范 # 客户端请求 string name uint32 money # 中间这三个横杠很重要 不能删掉 --- # 服务端响应 bool success uint32 money接口编译 修改…...

linux /www/server/cron内log文件占用空间过大,/www/server/cron是什么内容,/www/server/cron是否可以删除
linux服务器长期使用宝塔自带计划任务,计划任务执行记录占用服务器空间过大,导致服务器根目录爆满,需要长期排查并删除 /www/server/cron 占用空间过大问题处理 /www/server/cron是什么内容?/www/server/cron是否可以删除…...
C++青少年简明教程:break语句、continue语句
C青少年简明教程:break语句、continue语句 break语句 只能用在switch语句和循环语句(for循环、while循环和do-while循环)中。作用:跳出switch语句或提前终止循环。 break语句的基本语法如下: break; break语句的示例…...

MySQL实战行转列(或称为PIVOT)实战sales的表记录了不同产品在不同月份的销售情况,进行输出
有一个sales的表,它记录了不同产品在不同月份的销售情况: productJanuaryFebruaryMarchProduct AJanuary10Product AFebruary20Product BJanuary5Product BFebruary15Product CJanuary8Product CFebruary12 客户需求展示为如下的样子: pro…...

牛客NC164 最长上升子序列(二)【困难 贪心+二分 Java/Go/PHP/C++】
题目 题目链接: https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237 思路 贪心二分 所谓贪心,就是往死里贪,所以对于最大上升子序列,结尾元素越小,越有利于后面接上其他的数,也就可能变…...

电子烟开发【恒压、恒有效算法】
恒压算法 pwm是通过软件模拟的 pwm满值运行是250全占空比 #define D_TARGET_AVERAGE_VOLTAGE 3500 //R_ADC1_Vout :发热丝两端AD值 //R_ADC_FVR :电池电压AD值 //FVR_VOLTAGE :电池AD参考电压 满电值AD //R_Smk1Duty :最后…...
基于Open3D的点云处理22-非阻塞可视化/动态可视化
官网测试用例:examples/python/visualization/non_blocking_visualization.py 非阻塞可视化,即实时更新点云数据; 如下,动态可视化ICP的匹配过程: import open3d as o3d import numpy as npif __name__ == "__main__":o3d.utility.set_verbosity_level(o3d.ut…...
C++面试题其一
C和C的区别 C和C都是广泛使用的编程语言,但它们有显著的区别: 语言范式: C:是一种过程化编程语言,强调过程和函数的使用。C:是一种多范式编程语言,支持面向对象编程、泛型编程和过程化编程。 …...

CentOS7某天的samba服务搭建操作记录(还没成功)
#CentOS7 yum软件仓库阿里云 samba服务器配置失败 sensors成功了 (花了200元组装H61测试机,75元的主板只有一块能用,垃圾板但又不完全能用) 2024.5月的某天记录如下: https://blog.csdn.net/dszgf5717/article/details/53732182 …...

Qt Demo:基于TCP协议的视频传输Demo
目录 1.设计思路 2.Pro文件配置 3.头文件引入 4.界面设计 5.初始化设备函数 6.发起视频链接函数 7.初始化定时器模块函数 8.TCP链接模块函数 9.处理接收的数据线程函数 10.实现功能展示 设计思路 基于TCP协议的视频传输Demo,设计要实现的功能主要是TCP传输还有视频&…...

内存管理【C++】
内存分布 C中的内存区域主要有以下5种 栈(堆栈):存放非静态局部变量/函数参数/函数返回值等等,栈是向下增长的【地址越高越先被使用】。栈区内存的开辟和销毁由系统自动执行 堆:用于程序运行时动态内存分配ÿ…...

D3D 顶点格式学习
之前D3D画三角形的代码中有这一句, device.VertexFormat CustomVertex.TransformedColored.Format; 这是设置顶点格式; 画出的三角形如下, 顶点格式是描述一个三维模型的顶点信息的格式;可以包含以下内容, 位置…...

gmssl vs2010编译
1、虚拟机win10 x64,离线安装vs2010和2010sp1补丁; 2、安装ActivePerl_v5.28.1.0000和nasm-2.16.03-installer-x64均是默认完整安装; nasm官网下载: Index of /pub/nasm/releasebuilds/2.16.03/win64https://www.nasm.us/pub/nas…...

容器化部署gitlab、jenkins,jenkins应用示例
一、容器化部署docker和docker conpose安装 Docker&Docker-compose的安装及部署_docker 20 使用什么版本docker-compose-CSDN博客 1.docker 安装脚本 cat >01_docker.sh<<EOF #!/bin/bash yum remove docker \docker-client \docker-client-latest \docker-co…...

基于STM32的轻量级Web服务器设计
文章目录 一、前言1.1 开发背景1.2 实现的功能1.3 硬件模块组成1.4 ENC28J60网卡介绍1.5 UIP协议栈【1】目标与特点【2】核心组件【3】应用与优势 1.6 添加UIP协议栈实现创建WEB服务器步骤1.7 ENC28J60添加UIP协议栈实现创建WEB客户端1.8 ENC28J60移植UIP协议并编写服务器测试示…...
用r语言处理 Excel数据当中的缺失值方法
以下是使用 R 编程语言处理 Excel 缺失数据的一些常见方法示例代码:(无需循环) 读取包含缺失数据的 Excel 文件 data <- read.csv(“your_file.csv”) 查看数据中是否有缺失值 sum(is.na(data)) 用平均值填充缺失值 data c o l u m …...

AWS 高防和阿里云高防深度对比
随着网络攻击的不断增加,企业对于网络安全的需求也越来越高。在这种情况下,高防护服务成为了企业网络安全的重要组成部分。AWS和阿里云作为全球领先的云计算服务提供商,都提供了高防护服务,但它们之间存在着一些差异。我们九河云一…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...

自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...

七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...