当前位置: 首页 > 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类型…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...

LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》

&#x1f9e0; LangChain 中 TextSplitter 的使用详解&#xff1a;从基础到进阶&#xff08;附代码&#xff09; 一、前言 在处理大规模文本数据时&#xff0c;特别是在构建知识库或进行大模型训练与推理时&#xff0c;文本切分&#xff08;Text Splitting&#xff09; 是一个…...

Java后端检查空条件查询

通过抛出运行异常&#xff1a;throw new RuntimeException("请输入查询条件&#xff01;");BranchWarehouseServiceImpl.java // 查询试剂交易&#xff08;入库/出库&#xff09;记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...