排序算法:冒泡排序
冒泡排序是入门级的算法,但也有一些有趣的玩法。通常来说,冒泡排序有三种写法:
- 一边比较一边向后两两交换,将最大值 / 最小值冒泡到最后一位;
- 经过优化的写法:使用一个变量记录当前轮次的比较是否发生过交换,如果没有发生交换表示已经有序,不再继续排序;
- 进一步优化的写法:除了使用变量记录当前轮次是否发生交换外,再使用一个变量记录上次发生交换的位置,下一轮排序时到达上次交换的位置就停止比较。
冒泡排序的第一种写法
代码如下:
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…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
