网站开发时ie11的兼容/西安seo推广
冒泡排序是入门级的算法,但也有一些有趣的玩法。通常来说,冒泡排序有三种写法:
- 一边比较一边向后两两交换,将最大值 / 最小值冒泡到最后一位;
- 经过优化的写法:使用一个变量记录当前轮次的比较是否发生过交换,如果没有发生交换表示已经有序,不再继续排序;
- 进一步优化的写法:除了使用变量记录当前轮次是否发生交换外,再使用一个变量记录上次发生交换的位置,下一轮排序时到达上次交换的位置就停止比较。
冒泡排序的第一种写法
代码如下:
public static void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 如果左边的数大于右边的数,则交换,保证右边的数字最大swap(arr, j, j + 1);}}}
}
// 交换元素
private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}
最外层的 for 循环每经过一轮,剩余数字中的最大值就会被移动到当前轮次的最后一位,中途也会有一些相邻的数字经过交换变得有序。总共比较次数是 (n−1)+(n−2)+(n−3)+…+1。
这种写法相当于相邻的数字两两比较,并且规定:“谁大谁站右边”。经过 n−1 轮,数字就从小到大排序完成了。整个过程看起来就像一个个气泡不断上浮,这也是“冒泡排序法”名字的由来。
冒泡排序的第二种写法
代码如下:
public static void bubbleSort(int[] arr) {// 初始时 swapped 为 true,否则排序过程无法启动boolean swapped = true;for (int i = 0; i < arr.length - 1; i++) {// 如果没有发生过交换,说明剩余部分已经有序,排序完成if (!swapped) break;// 设置 swapped 为 false,如果发生交换,则将其置为 trueswapped = false;for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 如果左边的数大于右边的数,则交换,保证右边的数字最大swap(arr, j, j + 1);// 表示发生了交换swapped = true;}}}
}
// 交换元素
private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}
最外层的 for 循环每经过一轮,剩余数字中的最大值仍然是被移动到当前轮次的最后一位。这种写法相对于第一种写法的优点是:如果一轮比较中没有发生过交换,则立即停止排序,因为此时剩余数字一定已经有序了。
冒泡排序的第三种写法
第三种写法比较少见,它是在第二种写法的基础上进一步优化:
public static void bubbleSort(int[] arr) {boolean swapped = true;// 最后一个没有经过排序的元素的下标int indexOfLastUnsortedElement = arr.length - 1;// 上次发生交换的位置int swappedIndex = -1;while (swapped) {swapped = false;for (int i = 0; i < indexOfLastUnsortedElement; i++) {if (arr[i] > arr[i + 1]) {// 如果左边的数大于右边的数,则交换,保证右边的数字最大swap(arr, i, i + 1);// 表示发生了交换swapped = true;// 更新交换的位置swappedIndex = i;}}// 最后一个没有经过排序的元素的下标就是最后一次发生交换的位置indexOfLastUnsortedElement = swappedIndex;}
}
// 交换元素
private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}
经过再一次的优化,代码看起来就稍微有点复杂了。最外层的 while 循环每经过一轮,剩余数字中的最大值仍然是被移动到当前轮次的最后一位。
在下一轮比较时,只需比较到上一轮比较中,最后一次发生交换的位置即可。因为后面的所有元素都没有发生过交换,必然已经有序了。
*交换的技巧
一般来说,交换数组中两个数字的函数如下:
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
更好的方案是通过位运算完成数字交换:
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[i] ^ arr[j];
使用异或运算来进行交换时,要注意的是:参与运算的变量所指的地址不能相同,若有相同地址值参与运算,所得结果为0。
相关文章:

排序算法:冒泡排序
冒泡排序是入门级的算法,但也有一些有趣的玩法。通常来说,冒泡排序有三种写法: 一边比较一边向后两两交换,将最大值 / 最小值冒泡到最后一位;经过优化的写法:使用一个变量记录当前轮次的比较是否发生过交换…...

Spring事件监听源码解析
spring事件监听机制离不开容器IOC特性提供的支持,比如容器会自动创建事件发布器,自动识别用户注册的监听器并进行管理,在特定的事件发布后会找到对应的事件监听器并对其监听方法进行回调。Spring帮助用户屏蔽了关于事件监听机制背后的很多细节…...

Cpp学习——list的模拟实现
目录 一,实现list所需要包含的三个类 二,三个类的实现 1.list_node 2.list类 3.iterator_list类 三,功能实现 1.list类里的push_back() 2.iterator类里的运算符重载 3,list类里面的功能函数 1.insert(ÿ…...

工具推荐:Chat2DB一款开源免费的多数据库客户端工具
文章首发地址 Chat2DB是一款开源免费的多数据库客户端工具,适用于Windows和Mac操作系统,可在本地安装使用,也可以部署到服务器端并通过Web页面进行访问。 相较于传统的数据库客户端软件如Navicat、DBeaver,Chat2DB具备了与AIGC…...

C语言刷题指南(二)
📙作者简介: 清水加冰,目前大二在读,正在学习C/C、Python、操作系统、数据库等。 📘相关专栏:C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 👍…...

[C++11]
文章目录 1. 自动类型推导1.1 auto1.1.1 推导规则1.1.2 auto的限制1.1.3 auto的应用1.1.4 范围for 1.2 decltype1.2.1 推导规则1.2.2 decltype的应用 1.3 返回类型后置 2.可调用对象包装器、绑定器2.1 可调用对象包装器2.1.1 基本用法2.1.2 作为回调函数使用 2.2 绑定器 3. usi…...

【MySQL系列】--初识数据库
💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃个人主页 :阿然成长日记 …...

Unity导入google.protobuf失败,无法找到google命名空间
问题: 1.刚开始把protobuf的文件夹直接从其他项目里(unity2021)里复制到unity(2020)版本,当时报错protobuf.dll的依赖项system.memory版本不对。 2.没有使用原来的protobuf文件了。使用vs2019的NuGet管理包来下载Google.Protobuf ,仍然报错找…...

使用IDM下载视频出现“由于法律原因,IDM无法下载...
一、问题描述 由于法律原因,IDM无法下载..,如图: 二、原因分析 下载该IDM抓取的M3U8文件,查看其中的内容发现 : #EXT-X-KEY 字段已经写明了加密方式是AES-128,包含一个URI和IV值 #EXTM3U #EXT-X-VERSION:3 #EXT-X-TARGETDURATION:8 #EXT-X-MEDIA-SEQUENCE:0 #EXT-X-KEY:…...

pointnet C++推理部署--tensorrt框架
classification 如上图所示,由于直接export出的onnx文件有两个输出节点,不方便处理,所以编写脚本删除不需要的输出节点193: import onnxonnx_model onnx.load("cls.onnx") graph onnx_model.graphinputs graph.inpu…...

34.Netty源码之Netty如何处理网络请求
highlight: arduino-light 通过前面两节源码课程的学习,我们知道 Netty 在服务端启动时会为创建 NioServerSocketChannel,当客户端新连接接入时又会创建 NioSocketChannel,不管是服务端还是客户端 Channel,在创建时都会初始化自己…...

vscode 安装勾选项解释
1、通过code 打开“操作添加到windows资源管理器文件上下文菜单 :把这个两个勾选上,可以对文件使用鼠标右键,选择VSCode 打开。 2、将code注册为受支持的文件类型的编辑器:不建议勾选,这样会默认使用VSCode打开支持的相…...

Spring 6.0官方文档示例(24): replace-method的用法
一、原始bean定义 package cn.edu.tju.study.service.anno.domain;public class MyValueCalculator {public String computeValue(String input) {return "you inputted: " input;}// some other methods... }二、replace bean定义 package cn.edu.tju.study.serv…...

自然语言处理从入门到应用——LangChain:记忆(Memory)-[聊天消息记录]
分类目录:《自然语言处理从入门到应用》总目录 Cassandra聊天消息记录 Cassandra是一种分布式数据库,非常适合存储大量数据,是存储聊天消息历史的良好选择,因为它易于扩展,能够处理大量写入操作。 # List of contact…...

Python web实战之细说 Django 的单元测试
关键词: Python Web 开发、Django、单元测试、测试驱动开发、TDD、测试框架、持续集成、自动化测试 大家好,今天,我将带领大家进入 Python Web 开发的新世界,深入探讨 Django 的单元测试。通过本文的实战案例和详细讲解ÿ…...

pytorch 42 C#使用onnxruntime部署内置nms的yolov8模型
在进行目标检测部署时,通常需要自行编码实现对模型预测结果的解码及与预测结果的nms操作。所幸现在的各种部署框架对算子的支持更为灵活,可以在模型内实现预测结果的解码,但仍然需要自行编码实现对预测结果的nms操作。其实在onnx opset===11版本以后,其已支持将nms操作嵌入…...

【Lua】(一)VSCode 搭建 Lua 开发环境
前言 最近在找工作,基本所有的岗位都会问到 Lua(甚至拼 UI 的都要求会 Lua),咱能怎么办呢,咱也只能学啊…… 工欲善其事,必先利其器。第一步,先来把环境配置好吧! 当前适用版本&a…...

react-vite-antd环境下新建项目
vite 创建一个react项目 1. 安装vite并创建一个react项目1. 我使用的 yarn安装,基本配置项目名字, 框架react ,js2. cd vite-react进入项目目录安装node包并启动项目 2. 安装引入Ant Design引入依赖(我用的yarn,没有安装的也可以使…...

KeilMDk软仿真设置_STM32F03C8
1、KeilMDK软仿真的价值 (1)在没有硬件的情况下进行程序的编写调试。 (2)避免频繁的下载程序,延长单片机Flash寿命。 2、软仿真配置。 (1)打开Keil工程。 (2)点击“Options for Target ***”,如下图所示。 (3)点击“Debug”。 (4)进行如下配置。 U…...

mysql的隐式连接和显式连接的区别
隐式连接(Implicit Join)和显式连接(Explicit Join)是 SQL 查询中用于联结多个表的两种不同语法方式。它们的区别主要体现在语法的书写风格和可读性上。 隐式连接: 隐式连接使用逗号 , 将多个表名放在 FROM 子句中&am…...

vue-element-admin新增view后点击侧边栏加载慢问题
按照官网文档新增view 新增之后点击显示一直在加载中 解决方案:删除script中这段代码...

论文《LoRA: Low-Rank Adaptation of Large Language Models》阅读
论文《LoRA: Low-Rank Adaptation of Large Language Models》阅读 BackgroundIntroducitonProblem StatementMethodology Δ W \Delta W ΔW 的选择 W W W的选择 总结 今天带来的是由微软Edward Hu等人完成并发表在ICLR 2022上的论文《LoRA: Low-Rank Adaptation of Large Lan…...

MySQL数据类型篇
数值类型 类型有符号(SIGNED)取值范围无符号(UNSIGNED)取值范围大小描述TINYINT(-128,127)(0,255)1byte小整数值SMALLINT(-32768,32767)(0,65535)2bytes大整数值INT/INTEGER(-2147483648,2147483647)(0,429…...

Eureka注册中心
全部流程 注册服务中心 添加maven依赖 <!--引用注册中心--> <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-netflix-eureka-server</artifactId> </dependency> 配置Eureka 因为自…...

代码随想录算法训练营第53天|动态规划part14
8.19周六 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 动态规划 详细布置 1143.最长公共子序列 题目:两个字符串,问最长的公共子序列多长(不连续) 题解: 1、dp[i][j]:长度为[0, i - 1]的字…...

houdini xyzdist primuv 实现按路径走
2. meause distance v 0; add popforce...

Asrock-Z690-PG-Reptide i5-13600kf电脑 Hackintosh 黑苹果引导文件
硬件配置(需要下载请百度搜索:黑果魏叔) 硬件型号驱动情况主板 Asrock Z690 PG Reptide 处理器i5-13600kf RaptorLake (Undervolted)已驱动内存2x16Gb DDR4 3600 ADATA XPG已驱动硬盘1Tb Netac NV7000 NVME M2 (PCI-e 4.0)已驱动显卡Radeon …...

linux 搭建 nexus maven私服
目录 环境: 下载 访问百度网盘链接 官网下载 部署 : 进入目录,创建文件夹,进入文件夹 将安装包放入nexus文件夹,并解压编辑 启动 nexus,并查看状态.编辑 更改 nexus 端口为7020,并重新启动,访问虚拟机7020…...

MySQL中按月统计并逐月累加统计值的几种写法
有时候,我们可能有这样的场景,需要将销量按月统计,并且按月逐月累加。写惯了GROUP BY,按月统计倒是小case,但是逐月累加实现起来,要稍微麻烦一点。下面就整理几种写法,以备不时之需。 本月第一天 -- 本月第一天 SELE…...

音视频 FFmpeg音视频处理流程
ffmpeg -i test_1920x1080.mp4 -acodec copy -vcodec libx264 -s 1280x720 test_1280x720.flv推荐一个零声学院项目课,个人觉得老师讲得不错,分享给大家: 零声白金学习卡(含基础架构/高性能存储/golang云原生/音视频/Linux内核&am…...