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

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解

一、前言 在HarmonyOS 5的应用开发模型中&#xff0c;featureAbility是旧版FA模型&#xff08;Feature Ability&#xff09;的用法&#xff0c;Stage模型已采用全新的应用架构&#xff0c;推荐使用组件化的上下文获取方式&#xff0c;而非依赖featureAbility。 FA大概是API7之…...

从实验室到产业:IndexTTS 在六大核心场景的落地实践

一、内容创作&#xff1a;重构数字内容生产范式 在短视频创作领域&#xff0c;IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色&#xff0c;生成的 “各位吴彦祖们大家好” 语音相似度达 97%&#xff0c;单条视频播放量突破百万…...

MeshGPT 笔记

[2311.15475] MeshGPT: Generating Triangle Meshes with Decoder-Only Transformers https://library.scholarcy.com/try 真正意义上的AI生成三维模型MESHGPT来袭&#xff01;_哔哩哔哩_bilibili GitHub - lucidrains/meshgpt-pytorch: Implementation of MeshGPT, SOTA Me…...