【八大经典排序算法】冒泡排序
【八大经典排序算法】冒泡排序
- 一、概述
- 二、思路解读
- 三、代码实现
- 四、优化

一、概述
冒泡排序由于其简单和易于理解,使其成为初学者学习排序算法的首选,也是初学者接触到的第一个排序算法。其原理是通过重复交换相邻的元素来将最大的元素逐步“冒泡”到最后。冒泡排序由美国计算机科学家冯·诺伊曼(John von Neumann)于1945年提出。
冯·诺伊曼是计算机科学和现代计算机体系结构的奠基人之一,他在设计计算机算法时,意识到排序是计算机科学中的一个基本问题。于是,他提出了冒泡排序算法。
冒泡排序的思想是基于比较相邻元素的大小,如果顺序不正确,则交换它们的位置。通过多次遍历数组,每次都将最大的元素“冒泡”到末尾,最终实现整个数组的排序。
二、思路解读
我们知道冒泡排序的基本思想本思想是通过不断交换相邻元素的位置,将最大(或最小)的元素逐步“冒泡”到序列的末尾。(接下来以升序为例)
我们可以从序列的第一个元素开始,依次比较相邻的两个元素的大小。如果前一个元素大于后一个元素,则交换它们的位置,相当于将较大的元素冒泡到后面。然后继续对剩余的元素进行比较和交换,直到最后一个元素,此时最大的元素就成功冒泡到序列的末尾啦。
上述过程我们已经将整个排序中最大的数冒泡到了最尾端,接下啦要做的就是不断重复上述步骤,每次需比较和交换的范围缩小一个元素,直到整个序列有序为止。
动画演示:

三、代码实现
上述思路如何转换为代码呢?(以升序为例)
我们可以通过双重循环来实现。
第一层循环表示要排序的次数。假设我们有n个元素,此时我们只需要排序n-1次,让最后n-1个元素有序,此时剩余的最后一个元素一定是最小的。
第二层排序表示将每次排序中的最大数冒泡到最后。需要注意的是,我们每完成一次排序,待排序的元素个数就少1。
【代码】:
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void BubbleSort(int* a, int n)
{//排序n-1次for (int i = 0; i < n - 1; i++){//将最大元素冒泡到最后//为什么边界条件是n-1-i呢?//因为n个数,两两比较,即比较n-1对。同时每排序完i次,待排序的个数就减i。for (int j = 0; j < n - 1 - i; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}}}
}
四、优化
上述代码已经可以完整实现一个排序了。但有一个问题,如果我们带排序的数据接近有序呢?比如:

我们发现只需要简单交换1次即可。但按原来代码所示,一次过后虽然排序已经有序了,但还是要继续比较的。未免太死板了。
所以我们可以在每次排序前多加一个变量flag,每次排序过程中如果有数据交换,就改变flag的值。
最后,我们只需通过判断flag的值是否改变即可判断是否已经有序。如果flag的值没改变(以升序为例),则说明数据中后一项都比前一项大,此时数组有序。
【最终代码】:
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int flag = 1;for (int j = 0; j < n - 1 - i; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);flag = 0;}}if (flag)break;}
}
时间复杂度:O(N^2)
空间复杂度:O(1)


相关文章:
【八大经典排序算法】冒泡排序
【八大经典排序算法】冒泡排序 一、概述二、思路解读三、代码实现四、优化 一、概述 冒泡排序由于其简单和易于理解,使其成为初学者学习排序算法的首选,也是初学者接触到的第一个排序算法。其原理是通过重复交换相邻的元素来将最大的元素逐步“冒泡”到…...
【IEEE会议】第五届机器人、智能控制与人工智能国际学术会议(RICAI 2023)
【IEEE列表会议】第五届机器人、智能控制与人工智能国际学术会议(RICAI 2023) 2023 5th International Conference on Robotics, Intelligent Control and Artificial Intelligence 第五届机器人、智能控制与人工智能国际学术会议(RICAI 20…...
如何在本地 Linux 主机上实现 Yearning SQL 审核平台的远程访问?
文章目录 前言1. Linux 部署Yearning2. 本地访问Yearning3. Linux 安装cpolar4. 配置Yearning公网访问地址5. 公网远程访问Yearning管理界面6. 固定Yearning公网地址 前言 Yearning 简单, 高效的MYSQL 审计平台 一款MYSQL SQL语句/查询审计工具,为DBA与开发人员使用…...
android.support.multidex.MultiDexApplication:DexPathList
修改项目的build.gradle文件,使用multidex并添加multidex库作为依赖,如下所示: android { defaultConfig { ... minSdkVersion 21 targetSdkVersion 28 multiDexEnabled true } ... } dependencies { compile com.android.support:multidex…...
云HIS医院信息化系统:集团化管理,多租户机制,满足医院业务需求
随着云计算、大数据、物联网等新兴技术的迅猛发展,HIS模式的理念、运行机制更新,衍生出了新的HIS模式——云HIS。云HIS是基于云计算、大数据、互联网等高新技术研发的医疗卫生信息平台,它实现了医院信息化从局域网向互联网转型,并…...
Docker拉取nginx镜像,部署若依Vue前端
前言 本文主要用来描述,如何用nginx部署若依项目的前端。 一、Docker 拉取 Nginx镜像 命令:docker pull nginx 二、Vue项目打包 2.1 先配置线上后端路径 说明:由于我打包命令是 npm run build:stage ,所以项目生效的环境文…...
简单介绍神经网络中不同优化器的数学原理及使用特性【含规律总结】
当涉及到优化器时,我们通常是在解决一个参数优化问题,也就是寻找能够使损失函数最小化的一组参数。当我们在无脑用adam时,有没有斟酌过用这个是否合适,或者说凭经验能够有目的性换用不同的优化器?是否用其他的优化器可…...
JL653—一个基于ARINC653的应用程序仿真调试工具
JL653是安装在PC机Windows操作系统上面的一层接插件,它能够真实地模拟ARINC653标准规定的功能性行为,从而可以供研发人员在PC机Windows环境下高效、快速的进行基于ARINC653的应用程序的开发、调试等。 JL653提供了ARINC 653 Part 1中要求的以下服务&…...
MQTT Paho Android 支持SSL/TLS(亲测有效)
MQTT Paho Android 支持SSL/TLS(亲测有效) 登录时支持ssl的交互 这是调测登录界面设计 代码中对ssl/tls的支持 使用MqttAndroidClient配置mqtt客户端请求时,不加密及加密方式连接存在以下几点差异: url及端口差异 val uri: String if (tlsConnect…...
STM32——SPI通信
文章目录 SPI(Serial Peripheral Interface)概述:SPI的硬件连接:SPI的特点和优势:SPI的常见应用:SPI的工作方式和时序图分析:工作模式传输模式与时序分析工作流程 SPI设备的寄存器结构和寄存器设…...
Linux虚拟机局域网IP配置
前言 应用程序包部署在主机(Window)的虚拟机(Linux CentOS7)上,把主机当做一个服务器,在局域网中访问部署在主机上的应用程序,配置Linux网络。 文章如有侵权,无意为之,…...
MacOS删除.DS_Store文件
目录 .DS_Store是什么删除命令防止再生命令 .DS_Store是什么 在 Mac OS X 系统下,几乎绝大部分文件夹中都包含 .DS_Store 隐藏文件,这里保存着针对这个目录的特殊信息和设置配置,例如查看方式、图标大小以及这个目录的一些附属元数据。 而在…...
ARM Linux DIY(十一)板子名称、开机 logo、LCD 控制台、console 免登录、命令提示符、文件系统大小
文章目录 前言板子名称uboot Modelkernel 欢迎词、主机名 开机 logoLCD 控制台console 免登录命令提示符文件系统大小 前言 经过前面十篇文章的介绍,硬件部分调试基本完毕,接下来的文章开始介绍软件的个性化开发。 板子名称 uboot Model 既然是自己的…...
【Unity程序技巧】Unity中的单例模式的运用
👨💻个人主页:元宇宙-秩沅 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 秩沅 原创 👨💻 收录于专栏:Uni…...
java leetcodetop100 (3,4 )最长连续数列,移动零
top3 最长连续数列 给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 * * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 * * * * 示例 1: * * 输入:nums [100,…...
用Vite从零到一创建React+ts项目
方式一:使用create-react-app命令创建项目 1、使用以下命令初始化一个空的npm 项目 npm init -y 2、输入以下命令安装React npm i create-react-app ps:如果失败的话尝试(1:使用管理员身份执行命令(2:切换镜像重…...
HTTP状态码301(永久重定向)不同Web服务器的配置方法
文章目录 301状态码通常在那些情况下使用301永久重定向配置Nginx配置301永久重定向Windows配置IIS301永久重定向PHP下的301重定向Apache服务器实现301重定向 301重定向是否违反相关法规?推荐阅读 当用户或搜索引擎向服务器发出浏览请求时,服务器返回的HT…...
vue-element-admin项目部署 nginx动态代理 含Docker部署、 Jenkins构建
介绍三种方式: 1.直接部署到nginx中 2.用nginx docker镜像部署 3.使用Jenkins构建 1.直接用nginx部署 vue-element-admin项目下有两个.env文件,.env.production是生产环境的,.env.developpment是开发环境的 vue-element-admin默认用的是mock数…...
使用Python来写模拟Xshell实现远程命令执行与交互
一、模块 这里使用的是 paramiko带三方库 pip install paramiko二、效果图 三、代码实现(这里的IP,用户名,密码修改为自己对应服务器的) import paramiko import timeclass Linux(object):# 参数初始化def __init__(self, ip, us…...
mybatis 数据库字段为空or为空串 忽略条件过滤, 不为空且不为空串时才需nameParam过滤条件
name未配置视为不考虑name条件 select * from user where (( (ISNULL(name)) OR (name) ) OR name #{user.nameParam} ) 三个or语句 推荐这个 select * from user where ISNULL(name) OR name OR name #{user.nameParam} select * from user where ISNULL(name) OR …...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
