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

排序算法之详解冒泡排序

引入

  • 冒泡排序顾名思义,就是像冒泡一样,泡泡在水里慢慢升上来,由小变大。
  • 虽然冒泡排序和冒泡并不完全一样,但却可以帮助我们理解冒泡排序。

思路

  • 一组无序的数组,要求我们从小到大排列
    1. 我们可以先将最大的元素放在数组末尾
    2. 再将第二大的数放在数组的倒数第二个位置
    3. 再将第三大的数放在数组的倒数第三个位置
    4. 以此类推
  • 那么现在问题的关键就是如何将 第 n 大的数 放在 倒数第 n 个位置 ---> 交换
  • 下面是冒泡排序的gif动画,该图来自于菜鸟教程

实现

提醒

  • 现在我们假设无序数组长度为 n 即下标 [ 0 , n-1 ]
  • 当前元素下标为 i ,下一个元素的下标为 j

第一次遍历 [ 0 , n - 1- 1 ] ---> [ 0 , n -2 ]

  • 如果 当前元素 > 后一个元素 ,那么就交换两个元素 , 再进行下次遍历
  • 如果 当前元素 > 后一个元素 , 直接进行下次遍历
  • 直到遍历完成之后,最大的值就在一次一次的交换中被交换到了数组末尾
  • 思考:为什么是从 0 开始遍历 ,n-2 结束 ?
    1. 因为 j 为 i 的下一个元素下标 ,如果为 [ 0,n-1 ]的话 ,那么当前元素下标就可以为 n - 1,那么下一个元素的下标就为 n ,显然数组下标越界了
    2. 而且正因为是从 [ 0 , n -2] 范围遍历 ,刚好可以保证经过这一轮遍历后 ,最大的数在数组末尾 ( i = n - 2 【即为倒数第二个数】 ,j = i + 1【末尾数】)

第二次遍历 [ 0 , n - 1- 2]----> [ 0 , n -3 ]

  • 经过第一次遍历,我们已经将最大的数移动到了数组末尾,所以,我们不用在去对末尾以确定的数进行比较,我们可以减少次数,来提高效率
  • 再次引用第一次遍历的步骤

......
最后一次遍历 [ 0 , n - 1 - (n-1) ] ---- > [ 0 , 0 ]

  • 最后一次遍历的情况就是还剩下两个元素未进行排序的情况 ,即下标 0 和 下标 1 未进行排序
  • 只需对这两个元素进行排序后,就完成了这个数组的排序

怎么确定一共需要遍历几次及每次遍历的数组下标范围

  • 遍历次数问题
    • 我们先来做一个假设
      • 如果一个数组只有两个元素,那么应该遍历几次 ? 1 次
      • 如果一个数组只有三个元素,那么应该遍历几次 ? 2次
        • 第一次将最大的数放在最末尾 ,第二次将第二大的数放在倒数第二 , 第三大的元素自然而然就在倒数第三了【即第一个】 ,不用遍历
      • 如果一个数组只有四个元素,那么应该遍历几次 ? 3 次
        • 第一次将最大的数放在最末尾 ,第二次将第二大的数放在倒数第二 , 第三次将第三大的元素放在在倒数第三 ,剩下一个元素,不用排
      • 显而易见,如果有 n 个 元素 ,那么就需要遍历 n - 1 次
  • 每次遍历数组下标
    • 按照上面的实现部分
      • 第一次遍历我们需要数组的下标为 [ 0 , n -2 ]
      • 第二次遍历我们需要数组的下标为 [ 0 , n -3 ]
      • 第三次遍历我们需要数组的下标为 [ 0 , n -4 ]
    • 那么就有一个规律了 ,n - 2 , n - 3 , n - 4
      • 当我们正在进行第一次遍历时,用一个变量保存 m = 1 , 那么第一次遍历下标可以为 [ 0 , n -1 - m ]
      • 当我们正在进行第二次遍历时,用一个变量保存 m = 2 , 那么第一次遍历下标可以为 [ 0 , n -1 - m ]
      • 当我们正在进行第三次遍历时,用一个变量保存 m = 3 , 那么第一次遍历下标可以为 [ 0 , n -1 - m ]
      • 当我们正在进行最后一次遍历时,用一个变量保存 m = n - 1, 那么第一次遍历下标可以为 [ 0 , n -1 - m ] ---> [ 0 , n - 1 - (n -1) ]

代码实现

// 冒泡排序算法
public static int[] bubble(int[] ints){// 注意我这里使用的是 <  , 而不是我思路中的  <= , 可以自行更改 ,如果没想明白说明你还没有理解// 用 i 来表示一共需要遍历多少次for (int i = 0; i < ints.length-1; i++) {// 真正开始进行遍历 ,根据 i 的值 不同 ,j 就不同 ,也就是说每次大遍历中小遍历的次数不同for (int j = 0; j < ints.length-1-i; j++) {// 如果前一个元素 >  后一个元素 ,则交换if (ints[j] > ints[j+1]){int temp = ints[j];ints[j] = ints[j+1];ints[j+1] = temp;}// 继续下次遍历}}return ints;
}

 

 

相关文章:

排序算法之详解冒泡排序

引入 冒泡排序顾名思义&#xff0c;就是像冒泡一样&#xff0c;泡泡在水里慢慢升上来&#xff0c;由小变大。虽然冒泡排序和冒泡并不完全一样&#xff0c;但却可以帮助我们理解冒泡排序。 思路 一组无序的数组&#xff0c;要求我们从小到大排列 我们可以先将最大的元素放在数组…...

el-upload组件调用后端接口上传文件实践

要点说明&#xff1a; 使用:http-request覆盖默认的上传行为&#xff0c;可以添加除文件外的其他参数&#xff0c;注意此时仍需保留action属性&#xff0c;action可以传个空串给http-request属性绑定的函数&#xff0c;函数入参必须为param调用接口请求&#xff0c;注意 heade…...

深度学习-实验1

一、Pytorch基本操作考察&#xff08;平台课专业课&#xff09; 使用&#x1d413;&#x1d41e;&#x1d427;&#x1d42c;&#x1d428;&#x1d42b;初始化一个 &#x1d7cf;&#x1d7d1;的矩阵 &#x1d474;和一个 &#x1d7d0;&#x1d7cf;的矩阵 &#x1d475;&am…...

互联网医院开发|医院叫号系统提升就医效率

在这个数字化时代&#xff0c;互联网医院不仅改变了我们的生活方式&#xff0c;也深刻影响着医疗行业。医院叫号系统应运而生&#xff0c;它能够有效解决患者管理和服务方面的难题。不再浪费大量时间在排队上&#xff0c;避免患者错过重要信息。同时&#xff0c;医护工作效率得…...

手写 Mybatis-plus 基础架构(工厂模式+ Jdk 动态代理统一生成代理 Mapper)

这里写目录标题 前言温馨提示手把手带你解析 MapperScan 源码手把手带你解析 MapperScan 源码细节剖析工厂模式Jdk 代理手撕脚手架&#xff0c;复刻 BeanDefinitionRegistryPostProcessor手撕 FactoryBean代理 Mapper 在 Spring 源码中的生成流程手撕 MapperProxyFactory手撕增…...

【C++11算法】iota算法

文章目录 前言一、iota函数1.1 iota是什么&#xff1f;1.2 函数原型1.3 参数和返回值1.4 示例代码1.5 示例代码21.6 示例代码3 总结 前言 C标准库提供了丰富的算法&#xff0c;其中之一就是iota算法。iota算法用于填充一个区间&#xff0c;以递增的方式给每个元素赋予一个值。…...

付费加密音乐格式转换Mp3、Flac工具

一、工具介绍 这是一款免费的将付费加密音乐等多种格式转换Mp3 Flac工具,现在大部分云音乐公司,比如QQ音乐、酷我音乐、酷狗音乐、网易云音乐、虾米音乐(RIP🙏)等,都推出了自己专属的云音乐格式,这些格式一般只能在制定的播放器里播放,其它的播放软件并不支持,在很多情…...

React前端开发架构:构建现代响应式用户界面

在当今的Web应用开发中&#xff0c;React已经成为最受欢迎的前端框架之一。它的出色性能、灵活性和组件化开发模式&#xff0c;使得它成为构建现代响应式用户界面的理想选择。在这篇文章中&#xff0c;我们将探讨React前端开发架构的核心概念和最佳实践&#xff0c;以帮助您构建…...

Azure Bastion的简单使用

什么是Azure Bastion Azure Bastion 是一个提供安全远程连接到 Azure 虚拟机&#xff08;VM&#xff09;的服务。传统上&#xff0c;访问 VM 需要使用公共 IP 或者设立 VPN 连接&#xff0c;这可能存在一些安全风险。Azure Bastion 提供了一种更安全的方式&#xff0c;它是一个…...

深入理解高并发编程 - 深度解析ScheduledThreadPoolExecutor

ScheduledThreadPoolExecutor 继承自 ThreadPoolExecutor 并实现了 ScheduledExecutorService 接口&#xff0c;这使得它可以同时充当线程池和定时任务调度器。 构造方法 public ScheduledThreadPoolExecutor(int corePoolSize) {super(corePoolSize, Integer.MAX_VALUE, 0, …...

Android---- 一个完整的小项目(消防app)

前言&#xff1a; 针对不同群体的需求&#xff0c;想着应该拓展写方向。医疗app很受大家喜欢&#xff0c;就打算顺手写个消防app&#xff0c;里面基础框架还是挺简洁 规整的。登陆注册和本地数据库写的便于大家理解。是广大学子的毕设首选啊&#xff01; 此app主要为了传递 消防…...

XXX程序 详细说明

用于记录理解PC程序的程序逻辑 1、程序的作用 根据原作者的说明&#xff08;文件说明.txt&#xff09;&#xff0c;该程序 (PC.py) 的主要作用是提取某一个文件夹中的某个设备 (通过config中的信息看出来是Ag_T_8) 产生的日志文件&#xff0c;然后提取其中某些需要的数据&…...

perl下载与安装教程【工具使用】

Perl是一个高阶程式语言&#xff0c;由 Larry Wall和其他许多人所写&#xff0c;融合了许多语言的特性。它主要是由无所不在的 C语言&#xff0c;其次由 sed、awk&#xff0c;UNIX shell 和至少十数种其他的工具和语言所演化而来。Perl对 process、档案&#xff0c;和文字有很强…...

Chrome谷歌浏览器修改输入框自动填充样式

Chrome谷歌浏览器修改输入框自动填充样式 背景字体 背景 input:-webkit-autofill{-webkit-box-shadow:0 0 0 1000px #fff inset !important; }字体 input:-internal-autofill-selected {-webkit-text-fill-color: #000 !important; }...

Azure CLI 进行磁盘加密

什么是磁盘加密 磁盘加密是指在Azure中对虚拟机的磁盘进行加密保护的一种机制。它使用Azure Key Vault来保护磁盘上的数据&#xff0c;以防止未经授权的访问和数据泄露。使用磁盘加密&#xff0c;可以保护磁盘上的数据以满足安全和合规性要求。 参考文档&#xff1a;https://l…...

Java“牵手”根据关键词搜索(分类搜索)速卖通商品列表页面数据获取方法,速卖通API实现批量商品数据抓取示例

速卖通商城是一个网上购物平台&#xff0c;售卖各类商品&#xff0c;包括服装、鞋类、家居用品、美妆产品、电子产品等。要获取速卖通商品列表和商品详情页面数据&#xff0c;您可以通过开放平台的接口或者直接访问速卖通商城的网页来获取商品详情信息。以下是两种常用方法的介…...

商城-学习整理-高级-消息队列(十七)

目录 一、RabbitMQ简介(消息中间件)1、RabbitMQ简介&#xff1a;2、核心概念1、Message2、Publisher3、Exchange4、Queue5、Binding6、Connection7、Channel8、Consumer9、Virtual Host10、Broker 二、一些概念1、异步处理2、应用解耦3、流量控制5、概述 三、Docker安装RabbitM…...

Android Camere开发入门(1):初识Camera

Android Camere开发入门(1):初识Camera 初步了解 在Android开发中,相机(Camera)是一个常见而重要的功能模块。它允许我们通过设备的摄像头捕捉照片和录制视频,为我们的应用程序增加图像处理和视觉交互的能力。 随着Android系统的不断发展和更新,相机功能也不断改进和增…...

hive表的全关联full join用法

背景&#xff1a;实际开发中需要用到全关联的用法&#xff0c;之前没遇到过&#xff0c;现在记录一下。需求是找到两张表的并集。 全关联的解释如下&#xff1b; 下面建两张表进行测试 test_a表的数据如下 test_b表的数据如下&#xff1b; 写第一个full join 的SQL进行查询…...

PMP串讲

&#xff01;5种冲突解决策略 &#xff01;敏捷3355。 &#xff1f;PMP项目管理132种工具技术合集&#xff1a; 参考2&#xff1a;项目管理的132种工具 - 水之座 ?质量管理,有多少种图&#xff1a; ?风险管理,有多少种图&#xff1a; --参考&#xff1a;PMP相关的十八种…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...

HTML版英语学习系统

HTML版英语学习系统 这是一个完全免费、无需安装、功能完整的英语学习工具&#xff0c;使用HTML CSS JavaScript实现。 功能 文本朗读练习 - 输入英文文章&#xff0c;系统朗读帮助练习听力和发音&#xff0c;适合跟读练习&#xff0c;模仿学习&#xff1b;实时词典查询 - 双…...

Qt学习及使用_第1部分_认识Qt---Qt开发基本流程

前言 学以致用,通过QT框架的学习,一边实践,一边探索编程的方方面面. 参考书:<Qt 6 C开发指南>(以下称"本书") 标识说明:概念用粗体倾斜.重点内容用(加粗黑体)---重点内容(红字)---重点内容(加粗红字), 本书原话内容用深蓝色标识,比较重要的内容用加粗倾…...