【八大经典排序算法】冒泡排序
【八大经典排序算法】冒泡排序
- 一、概述
- 二、思路解读
- 三、代码实现
- 四、优化
一、概述
冒泡排序由于其简单和易于理解,使其成为初学者学习排序算法的首选,也是初学者接触到的第一个排序算法。其原理是通过重复交换相邻的元素来将最大的元素逐步“冒泡”到最后。冒泡排序由美国计算机科学家冯·诺伊曼(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 …...

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...

Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
xmind转换为markdown
文章目录 解锁思维导图新姿势:将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件(ZIP处理)2.解析JSON数据结构3:递归转换树形结构4:Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...