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

算法笔记【4】-冒泡排序法改进

一、冒泡排序缺点

冒泡排序是一种简单但效率较低的排序算法。冒泡排序通过比较相邻元素并交换位置来实现排序。具体而言,它从数组的第一个元素开始,依次比较相邻的两个元素,如果顺序错误则交换它们的位置,直到整个数组排好序为止。但是冒泡排序算法的时间复杂度为O(n^2),不管数据是否已经有序,都会进行比较。导致大数据量时执行效率低下,这里将探讨两种方式改进冒泡排序算法以降低时间复杂度

二、改进策略

在每一轮的内层循环中,如果没有交换元素,则说明数组已经有序,可以提前退出外层循环,避免不必要的比较操作。实际代码中可以在外层循环中加入是否进行数据交换的判断,直接退出循环,减少时间复杂度。以下是使用matlab编写的冒泡排序算法和改进冒泡排序算法的示例代码:

  • 冒泡排序算法函数
%% 冒泡排序函数
function [sortedArr,o] = bubbleSort(arr)n = length(arr);o = 0;%时间复杂度for i = 1:n-1for j = 1:n-io = o + 1;if arr(j) > arr(j+1)% 交换元素temp = arr(j);arr(j) = arr(j+1);arr(j+1) = temp;endendendsortedArr = arr;
end
  • 改进冒泡排序算法函数
%% 改进冒泡排序函数
function [sortedArr,o] = mbubbleSort(arr)n = length(arr);o = 0;%时间复杂度for i = 1:n-1flag = false;for j = 1:n-io = o + 1;if arr(j) > arr(j+1)% 交换元素temp = arr(j);arr(j) = arr(j+1);arr(j+1) = temp;flag = true;endendif flag == falsebreak;endendsortedArr = arr;
end
  • 调用
clc;
clear;
arr = [65, 9,11,12,25,22,34];
%% 常规冒泡排序
[sortedArr,o] = bubbleSort(arr);
disp("***********常规冒泡排序*****************************");
disp("排序前的数组:");
disp(arr);
disp("排序后的数组:");
disp(sortedArr);
disp("时间复杂度:");
disp(o);
%% 改进冒泡排序
[sortedArr,o] = mbubbleSort(arr);
disp("***********改进冒泡排序*****************************");
disp("排序前的数组:");
disp(arr);
disp("排序后的数组:");
disp(sortedArr);
disp("时间复杂度:");
disp(o);

三、性能分析与结论
如图所示为上述两种方式的打印结果
在这里插入图片描述

可知,通过改进策略对数组[65, 9,11,12,25,22,34]冒泡排序,可以吧时间复杂度从21降低至15。
实际上针对需要排序的数组对象,冒泡排序的时间复杂度可最高仍然是O(n^2),但在数组有序度比较高时,可以降低时间复杂度,在最好情况下,即数组已经有序时,时间复杂度可达到O(n)。
下面两图是针对同一组数据使用冒泡算法和改进冒泡算法的排序流程图。可以直观的看出两种方式的差异。

  • 常规冒泡排序法过程示意
    在这里插入图片描述

  • 改进冒泡排序法过程示意
    在这里插入图片描述

三、总结

改进冒泡排序算法仍然对于学习和理解基本排序算法有着重要意义。通过深入掌握冒泡排序的原理以及不断进行优化,我们可以更好地理解算法的设计思想,并为今后解决各类排序问题提供参考。然而,冒泡排序仍然不适用于大规模数据的排序,因为时间复杂度和数据的有序程度相关,不完全可控。在实际应用中,我们更倾向于使用其他高效的排序算法,如快速排序或归并排序。

相关文章:

算法笔记【4】-冒泡排序法改进

一、冒泡排序缺点 冒泡排序是一种简单但效率较低的排序算法。冒泡排序通过比较相邻元素并交换位置来实现排序。具体而言,它从数组的第一个元素开始,依次比较相邻的两个元素,如果顺序错误则交换它们的位置,直到整个数组排好序为止…...

cocos creator 资源管理

cocos creator 在使用过程中,经常需要动态加载远端资源,比日说 用户头像,龙骨动画皮肤资源,这些资源不可能都做成 预制体交给 cocos creator 帮助我们管理; 这个时候就需要我们 动态加载远端资源(但是 动态…...

好用的API调试工具推荐:Apipost

随着数字化转型的加速,API(应用程序接口)已经成为企业间沟通和数据交换的关键。而在API开发和管理过程中,API文档、调试、Mock和测试的协作显得尤为重要。Apipost正是这样一款一体化协作平台,旨在解决这些问题&#xf…...

贪心算法学习——最长单调递增子序列

目录 ​编辑 一,题目 二,题目接口 三,解题思路和代码 一,题目 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组…...

银行家算法(Python实现)

银行家算法,以及安全检测算法: import copy# 银行家算法(资源分配合法性) def BankersAlgorithm(Process_num, Resources_num, Request, Max, Available, Allocation, Need):PID Request[PID] # 获取发起请求的进程ID# Step1.如…...

安装终端 ·Terminator

安装终端 在 ROS 中,需要频繁的使用到终端,且可能需要同时开启多个窗口,推荐一款较为好用的终端:**Terminator。**效果如下: 1.安装 sudo apt install terminator2.添加到收藏夹 显示应用程序 —> 搜索 terminator —> 右击 选择 添…...

【Python文件操作的其他例子】

A.Python文件操作的其他例子 当然,以下是一些Python文件操作的其他例子: 1. 读取文件内容: with open(example.txt, r) as f:content f.read()print(content)这个例子会打开名为’example.txt’的文件,读取其内容,…...

使用Terraform管理已经存在的kubernates和默认的节点池

背景: 通过terraform resource "alicloud_cs_managed_kubernetes" "k8s" {...}创建集群时,会产生一个默认的节点池default-nodepool,但是如何去修改这个默认节点池的信息呢? 解决思路: 因为Ter…...

在HTML当中引入Vue控件,以element-ui为例

前情:需要实现一个同时满足按天、按周、按月选择的时间选择器,但是以HTML为基础写的都不太满足我的要求,要么只能按天选择,要么就是想选择久远的时间得点很久,除非自己写捷径,所以就看上了element-ui的这个…...

UE5实现相机水平矫正

UE5实现相机水平矫正 思路,用HIT获得基于相机视角的 离散采样点,然后根据距离相机距离进行权重分析。 距离越近,采样约中心,即越接近人眼注意点,最后算出加权平均高度,赋予给相机,相机将水平旋…...

Word插入Latex语句并编译为数学公式

WPS不可行,正版word可以(垃圾WPS) 选中Latex语句并按下Alt (此处以后补一张图) 该方法不需要额外安装什么插件哦!...

Google Play PolicyBytes 政策更新中文视频 | 2023 年 10 月

Google Play 持续帮助开发者开启成功出海之旅,为用户提供安全优质的应用。也感谢大家与我们携手合作,继续努力将 Google Play 打造为一个安全可信赖的平台。欢迎您观看 Google Play PolicyBytes 中文视频了解 2023 年 10 月政策更新内容,更及…...

pytorch-fastrcnn识别王者荣耀敌方英雄血条

文章目录 前言效果如下实现训练数据获得训练数据和测试数据yaml文件训练py画框文件的修改py测试py升级 前言 最近看王者荣耀视频看到了一个别人提供的一个百里自动设计解决方案,使用一个外设放在百里的二技能上,然后拖动外设在屏幕上滑动,当外设检测到有敌方英雄时外设自动松开…...

阿里云推出通义千问App,提供全方位的协助

🦉 AI新闻 🚀 阿里云推出通义千问App,提供全方位的协助 摘要:阿里云旗下大模型通义千问App登陆各大安卓应用市场,具有超大规模预训练模型,可在创意文案、办公助理、学习助手、趣味生活等方面协助用户。功…...

深入解析 Spring Framework 中 @Autowired 注解的实现原理

关于Autowired注解的作用 Autowired 注解在Spring中的作用是实现依赖注入(Dependency Injection),它用于自动装配(autowiring)Spring Bean 的依赖关系。具体来说, Autowired 注解有以下作用: …...

电脑数据文件恢复工具easyrecovery14中文版

当不小心将回收站的文件删除了怎么办?想找回但是不知道怎么找回需要的数据文件?别担心今天小编就为大家介绍一款非常专业的电脑数据文件恢复工具,easyrecovery14是由Ontrack专为电脑用户推出的一款专业的数据恢复软件,这款软件功能…...

Android NDK开发详解之Application.mk探秘

Android NDK开发详解之Application.mk探秘 概览变量APP_ASFLAGSAPP_ASMFLAGSAPP_BUILD_SCRIPTAPP_CFLAGSAPP_CLANG_TIDYAPP_CLANG_TIDY_FLAGSAPP_CONLYFLAGSAPP_CPPFLAGSAPP_CXXFLAGSAPP_DEBUGAPP_LDFLAGSAPP_MANIFESTAPP_MODULESAPP_OPTIMAPP_PLATFORMAPP_PROJECT_PATHAPP_STL…...

(草履虫都可以看懂的)PyQt子窗口向主窗口传递参数,主窗口接收子窗口信号、参数。

子窗口向主窗口发射信号。 只需要插入两行代码 class CodeSettingWindow(Ui_CodeSetting, QMainWindow):_signal pyqtSignal(int, int, int) # 这个信号要放在class之下,———init————函数上def __init__(self):# self.Win_X, self.Win_Y, self.CodeNum表示…...

Golang Web3钱包开发指南

简介 以太坊(Ethereum)是目前最受欢迎的区块链平台之一,它提供了智能合约功能和去中心化应用(DApps)的开发能力。在以太坊生态系统中,Web3钱包扮演着关键角色,允许用户管理账户和密钥、发送交易…...

Vue使用 IndexDB vue操作IndexDB数据库 Vue操作IndexDB数据库

Vue使用 IndexDB vue操作IndexDB数据库 Vue操作IndexDB数据库 Vue使用 IndexDB vue操作IndexDB数据库 Vue操作IndexDB数据库安装 IndexDB类库引入 localForage测试 新增数据、获取数据 Vue使用 IndexDB vue操作IndexDB数据库 Vue操作IndexDB数据库 大部分场景使用 LocalStore都…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

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

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