【数据结构和算法】排序算法
说明:以下排序如无特别说明,都是从小到大升序排序
1. 冒泡排序
核心思想:每个元素与其相邻元素比较,如果前者大于后者则交换,每次循环结束后会将最大值放到最后,像小水泡从底下冒到上面成大水泡一样,如此循环,较大元素会逐渐冒泡到后面,直到最小的元素在最前面,完成从小到大排序。
public static void bubbleSort(int[] arr) {for (int i = 0; i < arr.length; i++) {// 注意由于是与下一个元素比较,故这里必须是 j < arr.length-i-1for (int j = 0; j < arr.length - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;}}}
}
时间复杂度 O(n^2);空间复杂度O(1);不稳定排序;原地排序
优化:
public static void bubbleSort(int[] arr) {for (int i = 0; i < arr.length; i++) {// 增加一个是否需要继续的标志boolean flag = false;for (int j = 0; j < arr.length - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;flag = true;}}// 比较一轮后发现所有元素都无需交换,即认为本来是有序的if (!flag) {break;}}
}
2. 选择排序
核心思想:对长度为 n 的数组,循环 n-1 次,每次循环将当前元素与后面的元素比较找出最小元素并交换。
常规思路一:比较时交换
public static void selectSort1(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {int minIndex;for (int j = i + 1; j < arr.length; j++) {// 如果比当前元素小,就交换if (arr[j] < arr[i]) {minIndex = j;int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}}
}
优化思路二:比较完成后再交换
public static void selectSort(int[] arr) {// 每次循环找出最小元素索引,如果其与当前元素索引不同,则将其与当前元素索引交换for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}
}
时间复杂度 O(n^2);空间复杂度O(1);不稳定排序;原地排序
3. 插入排序
核心思想:从第二个元素开始将每个元素与其左边的元素对比,如果当前元素比其左边的元素小,就将其左边的元素往后移动,直到左边无比当前元素更大的元素,将当前元素插入到最左边,如此循环,较小的元素都会插入到合适的位置,最后完成排序。
public static void insertSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int insertValue = arr[i];int insertIndex = i - 1;while (insertIndex >= 0 && insertValue < arr[insertIndex]) {arr[insertIndex + 1] = arr[insertIndex];insertIndex--;}if (insertIndex + 1 != i) {arr[insertIndex + 1] = insertValue;}}
}
参考
[1] 十大基础算法
相关文章:

【数据结构和算法】排序算法
说明:以下排序如无特别说明,都是从小到大升序排序 1. 冒泡排序 核心思想:每个元素与其相邻元素比较,如果前者大于后者则交换,每次循环结束后会将最大值放到最后,像小水泡从底下冒到上面成大水泡一样&…...
Error: Cannot find module ‘@babel/core’处理
Error: Cannot find module babel/core’处理 问题产生的原因如何解决 在安装babel的时候,遇到个**Error: Cannot find module babel/core’**问题,查了很多资料才解决,希望能够帮助到各位兄弟。 问题产生的原因 babel-loader和babel-core版…...

K8S系列文章之 自动化运维利器 Fabric
Fabric 主要用在应用部署与系统管理等任务的自动化,简单轻量级,提供有丰富的 SSH 扩展接口。在 Fabric 1.x 版本中,它混杂了本地及远程两类功能;但自 Fabric 2.x 版本起,它分离出了独立的 Invoke 库,来处理…...
flask--->CBV/模板/请求响应/session
CBV 1 cbv写法-1 写个类,继承MethodView-2 在类中写跟请求方式同名的方法-3 注册路由:app.add_url_rule(/home, view_funcHome.as_view(home)) #home是endpoint,就是路由别名2 cbv加装饰器-方式一:class Home(MethodView):decor…...
Go语言基础:运算符、文件操作、接口、Packages、if else、for循环
文章目录 1.运算符2.文件操作3.接口4.Packages5.If else6.For循环 1.运算符 func main() {// 算术运算符a, b : 3, 7c : a bd : a - be : a * bf : a / bg : a % baa--fmt.Println(c, d, e, f, g)// 关系运算符fmt.Println(a b)fmt.Println(a ! b)fmt.Println(a < b)fmt.…...
2308C++学习简单协程文档
调试 用gdb/lldb p __coro_frame p __promise试 Try有三种状态:无状态,有异常,有值. 条件变量 主要区别在简单异步中条件变量面向Lazy协程.在条件变量上阻塞协程时,不会阻塞当前线程.用于多个协程间交互协作.基于协程版条件变量,多个协程可实现典型生产者消费者模型. 通知…...

C++笔记之从数组指针到函数数组指针(使用using name和std::function)
C笔记之从数组指针到函数数组指针(使用using name和std::function) 参考笔记: C之指针探究(三):指针数组和数组指针 C之指针探究(十三):函数指针数组 C之指针探究(二):一级指针和一维数组 C之指针探究(十一):函数名的…...

【数据结构】常见的排序算法
常见的排序算法 常见的排序算法插入排序之直接插入排序时间复杂度特性总结 插入排序之希尔排序时间复杂度 选择排序之直接选择排序特性总结 选择排序之堆排序时间复杂度特性总结 交换排序之冒泡排序特性总结 交换排序之快速排序hoare版本挖坑法双指针法快速排序的优化1…...

CentOS 安装 Jenkins
本文目录 1. 安装 JDK2. 获取 Jenkins 安装包3. 将安装包上传到服务器4. 修改 Jenkins 配置5. 启动 Jenkins6. 打开浏览器访问7. 获取并输入 admin 账户密码8. 跳过插件安装9. 添加管理员账户 1. 安装 JDK Jenkins 需要依赖 JDK,所以先安装 JDK1.8。输入以下命令&a…...
前端如何设置表格边框样式和单元格间距?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 实现思路⭐ 代码演示⭐ 注意事项⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个专栏是为那些对Web开发感兴…...

Ubuntu 22.04安装搜狗输入法
Ubuntu 22.04安装搜狗输入法 ubtuntu 22.04安装搜狗输入法 1. 添加中文语言支持2. 安装fcitx输入法框架3. 设置fcitx为系统输入法4. 设置fcitx开机启动,并卸载ibus输入法框架5. 安装搜狗输入法6. 重启电脑,调出搜狗输入法 1. 添加中文语言支持 Setti…...

【C++】初阶 --- 内联函数(inline)
文章目录 🥞内联函数🍟1、C语言实现"宏函数"🍟2、内联函数的概念🍟3、内联函数的特性🍟4、总结 🥞内联函数 🍟1、C语言实现"宏函数" 🥰用C语言先来实现普通的…...

VGGNet剪枝实战:使用VGGNet训练、稀疏训练、剪枝、微调等,剪枝出只有3M的模型
摘要 本文讲解如何实现VGGNet的剪枝操作。剪枝的原理:在BN层网络中加入稀疏因子,训练使得BN层稀疏化,对稀疏训练的后的模型中所有BN层权重进行统计排序,获取指定保留BN层数量即取得排序后权重阈值thres。遍历模型中的BN层权重&am…...

【iOS】GCD深入学习
关于GCD和队列的简单介绍请看:【iOS】GCD学习 本篇主要介绍GCD中的方法。 栅栏方法:dispatch_barrier_async 我们有时候需要异步执行两组操作,而且第一组操作执行完之后,才能开始执行第二组操作,当然操作组里也可以包含一个或者…...

Webpack开启本地服务器;HMR热模块替换;devServer配置;开发与生成环境的区分与配置
目录 1_开启本地服务器1.1_开启本地服务器原因1.2_webpack-dev-server 2_HMR热模块替换2.1_认识2.2_开启HMR2.3_框架的HMR 3_devServer配置3.1_host配置3.2_port、open、compress 4_开发与生成环境4.1_如何区分开发环境4.2_入口文件解析4.3_区分开发和生成环境配置 1_开启本地服…...

opencv 31-图像平滑处理-方框滤波cv2.boxFilter()
方框滤波(Box Filtering)是一种简单的图像平滑处理方法,它主要用于去除图像中的噪声和减少细节,同时保持图像的整体亮度分布。 方框滤波的原理很简单:对于图像中的每个像素,将其周围的一个固定大小的邻域内…...

Kubernetes关于cpu资源分配的设计
kubernetes资源 在K8s中定义Pod中运行容器有两个维度的限制: 资源需求(Requests):即运行Pod的节点必须满足运行Pod的最基本需求才能运行Pod。如 Pod运行至少需要2G内存,1核CPU。(软限制)资源限额(Limits):即运行Pod期间,可能内存使用量会增加,那最多能使用多少内存,这…...

Flink读取mysql数据库(java)
代码如下: package com.weilanaoli.ruge.vlink.flink;import com.ververica.cdc.connectors.mysql.source.MySqlSource; import com.ververica.cdc.connectors.mysql.table.StartupOptions; import com.ververica.cdc.debezium.JsonDebeziumDeserializationSchema; import org…...

小程序学习(五):WXSS模板语法
1.什么是WXSS WXSS是一套样式语言,用于美化WXML的组件样式,类似于网页开发中的CSS 2.WXSS和CSS的关系 WXSS模板样式-rpx 3.什么是rpx尺寸单位 4.rpx的实现原理 5.rpx与px之间的单位换算* WXSS模板样式-样式导入 6.什么是样式导入 使用WXSS提供的import语法,可以导入外联的样式…...
注解 @JsonFormat 与 @DateTimeFormat 的使用
文章目录 JsonFormat (双端互传)DateTimeFormat (前端传后端日期格式转化)情况一 前端是时间组件 <el-date-picker 或其他情况二 前端未设置组件 JsonFormat (双端互传) com.fasterxml.jackson.annotation.JsonFormat; 将字符串的时间转换成Date类型…...

IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
ubuntu22.04 安装docker 和docker-compose
首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

未授权访问事件频发,我们应当如何应对?
在当下,数据已成为企业和组织的核心资产,是推动业务发展、决策制定以及创新的关键驱动力。然而,未授权访问这一隐匿的安全威胁,正如同高悬的达摩克利斯之剑,时刻威胁着数据的安全,一旦触发,便可…...

【技巧】dify前端源代码修改第一弹-增加tab页
回到目录 【技巧】dify前端源代码修改第一弹-增加tab页 尝试修改dify的前端源代码,在知识库增加一个tab页"HELLO WORLD",完成后的效果如下 [gif01] 1. 前端代码进入调试模式 参考 【部署】win10的wsl环境下启动dify的web前端服务 启动调试…...
【Pandas】pandas DataFrame dropna
Pandas2.2 DataFrame Missing data handling 方法描述DataFrame.fillna([value, method, axis, …])用于填充 DataFrame 中的缺失值(NaN)DataFrame.backfill(*[, axis, inplace, …])用于**使用后向填充(即“下一个有效观测值”)…...
【NLP】 38. Agent
什么是 Agent? 一个 Agent 就是能够 理解、思考,并且进行世界交互 的模型系统,并不是纯粹的 prompt 返回器。 它可以: 读取外部数据(文件/API)使用记忆进行上下文维持用类Chain-of-Thought (CoT)方式进行…...