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

【数据结构和算法】排序算法

说明:以下排序如无特别说明,都是从小到大升序排序

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] 十大基础算法

相关文章:

【数据结构和算法】排序算法

说明&#xff1a;以下排序如无特别说明&#xff0c;都是从小到大升序排序 1. 冒泡排序 核心思想&#xff1a;每个元素与其相邻元素比较&#xff0c;如果前者大于后者则交换&#xff0c;每次循环结束后会将最大值放到最后&#xff0c;像小水泡从底下冒到上面成大水泡一样&…...

Error: Cannot find module ‘@babel/core’处理

Error: Cannot find module babel/core’处理 问题产生的原因如何解决 在安装babel的时候&#xff0c;遇到个**Error: Cannot find module babel/core’**问题&#xff0c;查了很多资料才解决&#xff0c;希望能够帮助到各位兄弟。 问题产生的原因 babel-loader和babel-core版…...

K8S系列文章之 自动化运维利器 Fabric

Fabric 主要用在应用部署与系统管理等任务的自动化&#xff0c;简单轻量级&#xff0c;提供有丰富的 SSH 扩展接口。在 Fabric 1.x 版本中&#xff0c;它混杂了本地及远程两类功能&#xff1b;但自 Fabric 2.x 版本起&#xff0c;它分离出了独立的 Invoke 库&#xff0c;来处理…...

flask--->CBV/模板/请求响应/session

CBV 1 cbv写法-1 写个类&#xff0c;继承MethodView-2 在类中写跟请求方式同名的方法-3 注册路由&#xff1a;app.add_url_rule(/home, view_funcHome.as_view(home)) #home是endpoint&#xff0c;就是路由别名2 cbv加装饰器-方式一&#xff1a;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) 参考笔记&#xff1a; C之指针探究(三)&#xff1a;指针数组和数组指针 C之指针探究(十三)&#xff1a;函数指针数组 C之指针探究(二)&#xff1a;一级指针和一维数组 C之指针探究(十一)&#xff1a;函数名的…...

【数据结构】常见的排序算法

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

CentOS 安装 Jenkins

本文目录 1. 安装 JDK2. 获取 Jenkins 安装包3. 将安装包上传到服务器4. 修改 Jenkins 配置5. 启动 Jenkins6. 打开浏览器访问7. 获取并输入 admin 账户密码8. 跳过插件安装9. 添加管理员账户 1. 安装 JDK Jenkins 需要依赖 JDK&#xff0c;所以先安装 JDK1.8。输入以下命令&a…...

前端如何设置表格边框样式和单元格间距?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 实现思路⭐ 代码演示⭐ 注意事项⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏是为那些对Web开发感兴…...

Ubuntu 22.04安装搜狗输入法

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

【C++】初阶 --- 内联函数(inline)

文章目录 &#x1f95e;内联函数&#x1f35f;1、C语言实现"宏函数"&#x1f35f;2、内联函数的概念&#x1f35f;3、内联函数的特性&#x1f35f;4、总结 &#x1f95e;内联函数 &#x1f35f;1、C语言实现"宏函数" &#x1f970;用C语言先来实现普通的…...

VGGNet剪枝实战:使用VGGNet训练、稀疏训练、剪枝、微调等,剪枝出只有3M的模型

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

【iOS】GCD深入学习

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

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()

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

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 &#xff08;前端传后端日期格式转化&#xff09;情况一 前端是时间组件 <el-date-picker 或其他情况二 前端未设置组件 JsonFormat (双端互传) com.fasterxml.jackson.annotation.JsonFormat; 将字符串的时间转换成Date类型…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

自然语言处理——Transformer

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

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 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…...

未授权访问事件频发,我们应当如何应对?

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

【技巧】dify前端源代码修改第一弹-增加tab页

回到目录 【技巧】dify前端源代码修改第一弹-增加tab页 尝试修改dify的前端源代码&#xff0c;在知识库增加一个tab页"HELLO WORLD"&#xff0c;完成后的效果如下 [gif01] 1. 前端代码进入调试模式 参考 【部署】win10的wsl环境下启动dify的web前端服务 启动调试…...

【Pandas】pandas DataFrame dropna

Pandas2.2 DataFrame Missing data handling 方法描述DataFrame.fillna([value, method, axis, …])用于填充 DataFrame 中的缺失值&#xff08;NaN&#xff09;DataFrame.backfill(*[, axis, inplace, …])用于**使用后向填充&#xff08;即“下一个有效观测值”&#xff09…...

【NLP】 38. Agent

什么是 Agent&#xff1f; 一个 Agent 就是能够 理解、思考&#xff0c;并且进行世界交互 的模型系统&#xff0c;并不是纯粹的 prompt 返回器。 它可以&#xff1a; 读取外部数据&#xff08;文件/API&#xff09;使用记忆进行上下文维持用类Chain-of-Thought (CoT)方式进行…...