【数据结构和算法】排序算法
说明:以下排序如无特别说明,都是从小到大升序排序
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类型…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
