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

【基础算法】之 冒泡排序优化

冒泡排序思想

基本思想: 冒泡排序,类似于水中冒泡,较大的数沉下去,较小的数慢慢冒起来(假设从小到大),即为较大的数慢慢往后排,较小的数慢慢往前排。
直观表达,每一趟遍历,将一个最大的数移到序列末尾

下图演示排序流程:

下面是传统冒泡排序写法 时间复杂度O(n^2):

public static void bubbleSort(int[] nums) {int length = nums.length;for (int i = 0; i < length; i++) {System.out.println("i=" + i);for (int j = 0; j + 1 < length -i; j++) {System.out.println("内层循环次数:====================-" + j);if (nums[j] > nums[j + 1]) {int tem = nums[j];nums[j] = nums[j + 1];nums[j + 1] = tem;}}System.out.println("=======第" + i + " 轮外循环执行==============================");for (Integer integer : nums) {System.out.println(integer);}}}

执行下看看效果:

第一轮 5次 ,第二轮 4次,第三轮 3次, 第四轮 2次 ,第五轮 1次 ,第六轮0次

但是当我们遇到下面这种序列

即: 1,2,3,5,4 我们只需要排一趟就可以了 而无需后续的循环。

初次优化:

基于这种情况我们给出了下面这种优化。

通过增加一个标志位 flag ,若在某轮「内循环」中未执行任何交换操作,则说明数组已经完成排序,直接返回结果即可。

public static void bubbleSort1(int[] nums) {int length = nums.length;//定义标志位标记已经有序或无序boolean flag = false;for (int i = 0; i < length; i++) {System.out.println("i=" + i);flag = true;for (int j = 0; j + 1 < length - i; j++) {System.out.println("内层循环次数:====================-" + j);if (nums[j] > nums[j + 1]) {int tem = nums[j];nums[j] = nums[j + 1];nums[j + 1] = tem;//交换后对flag置false,表示已经处理成有序flag = false;}}// 已经排好序了 无需后续循环了if (flag) {break;}System.out.println("=======第" + i + " 轮外循环执行==============================");for (Integer integer : nums) {System.out.println(integer);}}}

在看下执行效果:

第一轮 5次 ,第二轮 4次,第三轮 3次 ,第四轮 2次

很明显外层减少了循环次数

优化后的冒泡排序的最差和平均时间复杂度仍为 O(N^2) ;在输入数组 已排序 时,达到 最佳时间复杂度 O(N) 。

继续优化:

然而这种优化只能做到某一次已经排好序的时候我们直接跳跳出来,基于第一种优化我们得到一种启发:当一个数组接近有序的时候我们往往只需要在某一个小范围内排序即可,我们可以用一个标记来表示这个范围的下限,例如遇到下面的情况

然而我们发现,每次排序前或排序后数组的后面都有一部分已经有序,这时我们只要记下最后一次排下的数组的下标,下次排序的时候就可以只排序到此下标位置即可

目的就是减少内层循环比较的次数

public static void bubbleSort2(int[] nums) {int length = nums.length;int index = length;//每一次我们找到无序区的上界int maxIndex = 0;//定义标志位标记已经有序或无序boolean flag = false;for (int i = 0; i < length; i++) {System.out.println("i=" + i);flag = true;for (int j = 0; j + 1 < index; j++) {System.out.println("内层循环次数:====================-" + j);if (nums[j] > nums[j + 1]) {int tem = nums[j];nums[j] = nums[j + 1];nums[j + 1] = tem;//交换后对flag置false,表示已经处理成有序flag = false;//注意不要在这里直接将index置为jmaxIndex = j + 1;}}// 已经排好序了 无需后续循环了if (flag) {break;}//若排序过则将index置为最后一次交换的坐标,若没有则表示已经有序index = maxIndex;System.out.println("=======第" + i + " 轮外循环执行==============================");for (Integer integer : nums) {System.out.println(integer);}}}

再次执行看看效果:

第一轮 5次 ,第二轮 3次,第三轮 2次 ,第四轮 1次

很明显内层循环也减少了很多

优化后的冒泡排序的最差和平均时间复杂度仍为 O(N^2) ;在输入数组 已排序 时,达到 最佳时间复杂度 O(1) 。

其实还可以再优化, 一层外循环 执行2个同级的内循环( 正着扫描得到最大值, 反着扫描得到最小值)

总结

主要从以下2方面优化了传统的冒泡排序写法

// 1、减少外层循环次数
// 2、减少内层循环次数

相关文章:

【基础算法】之 冒泡排序优化

冒泡排序思想基本思想: 冒泡排序&#xff0c;类似于水中冒泡&#xff0c;较大的数沉下去&#xff0c;较小的数慢慢冒起来&#xff08;假设从小到大&#xff09;&#xff0c;即为较大的数慢慢往后排&#xff0c;较小的数慢慢往前排。直观表达&#xff0c;每一趟遍历&#xff0c;…...

Python | 线程锁 | 3分钟掌握【同步锁】(Threading.Lock)

文章目录概念无锁加锁死锁解决死锁概念 threading.Lock 同步锁&#xff0c;可以用于保证多个线程对共享数据的独占访问。 当一个线程获取了锁之后&#xff0c;其他线程在此期间将不能再次获取该锁&#xff0c;直到该线程释放锁。这样就可以保证共享数据的独占访问&#xff0c…...

Linux下安装MySQL8.0的详细步骤(解压tar.xz安装包方式安装)

Linux下安装MySQL8.0的详细步骤 第一步&#xff1a;下载安装配置 第二步&#xff1a;修改密码&#xff0c;并设置远程连接&#xff08;为了可以在别的机器下面连接该mysql&#xff09; 第三步&#xff1a;使用Navicat客户端连接 搞了一台云服务器&#xff0c;首先要干的活就是…...

leaflet 绘制多个点的envelope矩形(082)

第082个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+leaflet中如何根据多边形的几个坐标点来绘制envelope矩形。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果. 文章目录 示例效果配置方式示例源代码(共78行)安装插件相关API参考:专栏目标示例…...

CAJ论文怎么批量免费转换成Word

大家都知道CAJ文件吗&#xff1f;这是中国学术期刊数据库中的文件&#xff0c;这种文件类型比较特殊。如果想要提取其中的内容使用&#xff0c;该如何操作呢&#xff1f;大家可以试试下面这种免费的caj转word的方法,多个文档也可以一起批量转换。准备材料&#xff1a;CAJ文档、…...

面试必问: 结构体大小的计算方法

结构体大小的计算需同时满足以下几点 一、结构体成员的偏移量必须是当前成员大小的整数倍。&#xff08;0是任何数的整数倍&#xff09; 举一个例子 struct Test1{char a; // 当前偏移量为0&#xff0c;是char所占字节数1的整数倍 所以所占大小为1char b; …...

Java中super函数的用法

1 问题 Java中super函数有很多方法&#xff0c;在使用的时候我们应该如何正确区分&#xff1f; 2 方法 三种用法&#xff1a; 访问父类的方法。 调用父类构造方法。 访问父类中的隐藏成员变量。 class A{ int x,y; A(int x,int y){ System.out.println("A"); } } cla…...

第十一届“泰迪杯”数据挖掘挑战赛携“十万”大奖火热来袭

第十一届“泰迪杯”数据挖掘挑战赛 竞赛组织 主办单位&#xff1a; 泰迪杯数据挖掘挑战赛组织委员会 承办单位&#xff1a; 广东泰迪智能科技股份有限公司 人民邮电出版社 协办单位&#xff1a; 重庆市工业与应用数学学会、广东省工业与应用数学学会、广西数学学会、河北省工业…...

分享三个可以在家做的正规兼职工作,看到就是赚到

你可以在家做正式的兼职工作。在线兼职工作值得考虑&#xff0c;时间相对自由。在线兼职收入可能不如线下滴滴和外卖立竿见影&#xff0c;但仍然可以坚持收入。有些人比工作工资发展得更高。当然&#xff0c;天上不会有馅饼&#xff0c;不劳无获。那么有哪些正规的兼职可以在家…...

javaFx实现鼠标穿透画布,同时操作画布和桌面,背景透明,类似ppt批注

一、功能需要由来和大致效果 今天&#xff0c;我们要用javaFx来实现一个鼠标穿透画布的功能&#xff0c;该需求来自于在我们的javaFx桌面应用中&#xff0c;需要实现一个悬浮的桌面侧边工具栏&#xff0c;在工具栏中有画笔绘制&#xff0c;批注的功能&#xff0c;能够实现在任何…...

客户服务知识库的最佳实践7个步骤

每个公司的声誉都依赖于客户&#xff0c;如果客户因为想要购买你的产品找到你&#xff0c;但是了解到你的客户服务做的不好&#xff0c;可能也会放弃你的产品&#xff0c;就像市场营销依赖于潜在客户的关系一样&#xff0c;公司的服务部门也需要依赖于现有客户的关系&#xff0…...

多重继承的虚函数表

同一个类,不同对象使用同一张虚函数表 不同类使用不同的虚函数表 子类自己添加的虚函数(非重写),在VS中是将此放在第一个继承类的虚函数表里. #include <iostream> using namespace std;class Father { public:virtual void func1() { cout << "Father::f…...

第11篇:Java开发工具使用和代码规范配置

目录 1、IntelliJ IDEA 简介 2. IntelliJ IDEA 下载 3. IntelliJ IDEA 安装和使用 3.1 安装到Windows下 3.2 快速编写 Hello World 程序...

Rust模式匹配

模式匹配 模式匹配是从函数式编程语言&#xff08;例如&#xff1a;Haskell&#xff0c;Lisp&#xff09;吸收而来的&#xff0c;用于为复杂的类型系统提供一个轻松的解构能力。rust使用match来提供模式匹配的功能。mathc类似于其它编程语言中的switch-case&#xff0c;但是远…...

GIT:【基础一】必要配置和命令

目录 一、Git安装 二、基础命令 1.git config -l&#xff1a;git配置详细信息 2.git config --system -l&#xff1a;本地git系统自动配置的信息 3.git config --global -l&#xff1a;本地git用户自动配置的信息 4.where git&#xff1a; windows查看git安装目录 5.git各配置…...

黑马程序员-Linux系统编程-01

课程链接 01-Linux命令基础习惯-Linux系统编程_哔哩哔哩_bilibili 课程重点笔记 01-linux命令基础习惯 终端 终端&#xff1a;一切输入、输出的总称&#xff0c;因此终端并不是一定指的是命令行&#xff0c;只要是能进行输入或者输出即可&#xff0c;但是在linux终端上‘’内…...

Python|每日一练|动态规划|图算法|散列表|数组|双指针|单选记录:不同路径|求两个给定正整数的最大公约数和最小公倍数|删除有序数组中的重复项

1、不同路径&#xff08;数学&#xff0c;动态规划&#xff09; 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish”…...

Java常用框架(一)

思维导图 常见知识点 一、SpringBoot 1.简单介绍一下Spring及其优缺点 1.1 概念 重量级企业开发框架EJB的替代品&#xff0c;通过依赖注入、面向切面编程&#xff0c;使用简单Java对象POJO为企业Java开发提供了相对简单的方法。 1.2 优缺点 1.2.1 优点 组件代码轻量级 …...

基于 DSP+FPGA 的高清图像跟踪系统研制

目标识别与跟踪技术是目前图像处理研究的重点方向&#xff0c;在军事和民用领域中 具有广泛的应用价值&#xff0c;如精确制导武器、导弹飞机预警等军事领域&#xff0c;如交通管理、 刑事侦查等民用领域。其中&#xff0c;如何在复杂的背景中&#xff0c;提取、识别与跟踪特定…...

apisix部署

使用k8s部署前打包镜像&#xff1a; FROM centos:7 ARG APISIX_VERSION2.11.0 LABEL apisix_version“${APISIX_VERSION}” RUN yum install -y https://repos.apiseven.com/packages/centos/apache-apisix-repo-1.0-1.noarch.rpm && yum install -y https://repos…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...