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

排序算法:冒泡排序

冒泡排序是入门级的算法,但也有一些有趣的玩法。通常来说,冒泡排序有三种写法:

  • 一边比较一边向后两两交换,将最大值 / 最小值冒泡到最后一位;
  • 经过优化的写法:使用一个变量记录当前轮次的比较是否发生过交换,如果没有发生交换表示已经有序,不再继续排序;
  • 进一步优化的写法:除了使用变量记录当前轮次是否发生交换外,再使用一个变量记录上次发生交换的位置,下一轮排序时到达上次交换的位置就停止比较。

冒泡排序的第一种写法

代码如下:

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。

相关文章:

排序算法:冒泡排序

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

Spring事件监听源码解析

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

Cpp学习——list的模拟实现

目录 一&#xff0c;实现list所需要包含的三个类 二&#xff0c;三个类的实现 1.list_node 2.list类 3.iterator_list类 三&#xff0c;功能实现 1.list类里的push_back() 2.iterator类里的运算符重载 3&#xff0c;list类里面的功能函数 1.insert&#xff08;&#xff…...

工具推荐:Chat2DB一款开源免费的多数据库客户端工具

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

C语言刷题指南(二)

&#x1f4d9;作者简介&#xff1a; 清水加冰&#xff0c;目前大二在读&#xff0c;正在学习C/C、Python、操作系统、数据库等。 &#x1f4d8;相关专栏&#xff1a;C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 &#x1f44d…...

[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系列】--初识数据库

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …...

Unity导入google.protobuf失败,无法找到google命名空间

问题&#xff1a; 1.刚开始把protobuf的文件夹直接从其他项目里(unity2021)里复制到unity(2020)版本&#xff0c;当时报错protobuf.dll的依赖项system.memory版本不对。 2.没有使用原来的protobuf文件了。使用vs2019的NuGet管理包来下载Google.Protobuf &#xff0c;仍然报错找…...

使用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 如上图所示&#xff0c;由于直接export出的onnx文件有两个输出节点&#xff0c;不方便处理&#xff0c;所以编写脚本删除不需要的输出节点193&#xff1a; import onnxonnx_model onnx.load("cls.onnx") graph onnx_model.graphinputs graph.inpu…...

34.Netty源码之Netty如何处理网络请求

highlight: arduino-light 通过前面两节源码课程的学习&#xff0c;我们知道 Netty 在服务端启动时会为创建 NioServerSocketChannel&#xff0c;当客户端新连接接入时又会创建 NioSocketChannel&#xff0c;不管是服务端还是客户端 Channel&#xff0c;在创建时都会初始化自己…...

vscode 安装勾选项解释

1、通过code 打开“操作添加到windows资源管理器文件上下文菜单 &#xff1a;把这个两个勾选上&#xff0c;可以对文件使用鼠标右键&#xff0c;选择VSCode 打开。 2、将code注册为受支持的文件类型的编辑器&#xff1a;不建议勾选&#xff0c;这样会默认使用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)-[聊天消息记录]

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

Python web实战之细说 Django 的单元测试

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

pytorch 42 C#使用onnxruntime部署内置nms的yolov8模型

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

【Lua】(一)VSCode 搭建 Lua 开发环境

前言 最近在找工作&#xff0c;基本所有的岗位都会问到 Lua&#xff08;甚至拼 UI 的都要求会 Lua&#xff09;&#xff0c;咱能怎么办呢&#xff0c;咱也只能学啊…… 工欲善其事&#xff0c;必先利其器。第一步&#xff0c;先来把环境配置好吧&#xff01; 当前适用版本&a…...

react-vite-antd环境下新建项目

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

KeilMDk软仿真设置_STM32F03C8

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

mysql的隐式连接和显式连接的区别

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

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...