【算法】冒泡排序
目录
一、算法概述
二、算法原理
1. 核心思想
2. 排序过程演示
三、标准实现代码
四、时间复杂度分析
五、优化策略
1. 提前终止优化
2. 记录最后交换位置
六、算法特性
七、实际应用
八、扩展思考
九、总结
一、算法概述
冒泡排序(Bubble Sort)是最经典的排序算法之一,其名称源于元素移动方式如同水中气泡上浮的过程。这个简单直观的算法诞生于1956年,至今仍是计算机科学入门教育的经典案例。
二、算法原理
1. 核心思想
通过相邻元素的比较和交换,使较大元素逐步"浮"到数列末端。每一轮排序将确定一个元素的最终位置,类似于气泡从水底升到水面。
2. 排序过程演示
以数组 [5, 3, 8, 1, 2] 为例:
初始:5 3 8 1 2
第1轮:
3 5 8 1 2 → 比较5和3
3 5 1 8 2 → 比较8和1
3 5 1 2 8 → 比较8和2(确定最大值8)第2轮:
3 1 5 2 8 → 比较5和1
3 1 2 5 8 → 比较5和2(确定次大值5)第3轮:
1 3 2 5 8 → 比较3和1
1 2 3 5 8 → 比较3和2(确定中间值3)第4轮:
1 2 3 5 8 → 比较2和1(完全有序)
三、标准实现代码
def bubble_sort(arr):n = len(arr)for i in range(n):# 每次减少比较范围for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arr
四、时间复杂度分析
-
最好情况(已有序):O(n) (优化版)
-
平均情况:O(n²)
-
最坏情况(完全逆序):O(n²)
空间复杂度:O(1)(原地排序)
五、优化策略
1. 提前终止优化
def optimized_bubble_sort(arr):n = len(arr)for i in range(n):swapped = Falsefor j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]swapped = Trueif not swapped:breakreturn arr
2. 记录最后交换位置
def improved_bubble_sort(arr):n = len(arr)last_swap = n - 1while last_swap > 0:new_swap = 0for j in range(last_swap):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]new_swap = jlast_swap = new_swapreturn arr
六、算法特性
-
稳定性:稳定排序(相同元素相对位置不变)
-
适用场景:
-
小规模数据排序
-
教学演示用途
-
数据基本有序时表现良好
-
-
缺点:
-
大规模数据效率低下
-
元素移动次数较多
-
七、实际应用
-
硬件资源受限的嵌入式系统
-
图形界面中的简单数据排序
-
其他排序算法的基准测试对比
-
链表数据的排序(相比数组更具优势)
八、扩展思考
-
双向冒泡排序(鸡尾酒排序):交替进行正向和反向遍历
-
结合插入排序的混合算法
-
并行化处理的可能性
九、总结
冒泡排序虽不是最高效的排序算法,但其简明性使其成为:
-
理解排序思想的绝佳范例
-
算法优化的典型研究对象
-
其他高级排序算法的基础参照
在真实开发中,当数据规模超过1000时建议使用更高效的算法(如快速排序、归并排序)。但对于算法学习者,深入理解冒泡排序将有助于建立基础的算法思维模式。
附录:不同语言实现示例
// Java实现
public static void bubbleSort(int[] arr) {boolean swapped;for (int i = 0; i < arr.length-1; i++) {swapped = false;for (int j = 0; j < arr.length-i-1; j++) {if (arr[j] > arr[j+1]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;swapped = true;}}if (!swapped) break;}
}
相关文章:
【算法】冒泡排序
目录 一、算法概述 二、算法原理 1. 核心思想 2. 排序过程演示 三、标准实现代码 四、时间复杂度分析 五、优化策略 1. 提前终止优化 2. 记录最后交换位置 六、算法特性 七、实际应用 八、扩展思考 九、总结 一、算法概述 冒泡排序(Bubble Sort࿰…...
R Excel 文件:高效数据处理的利器
R Excel 文件:高效数据处理的利器 在数据分析领域,R语言因其强大的统计分析和可视化功能而备受推崇。而R Excel文件,作为R语言与Excel的桥梁,使得数据在R和Excel之间的高效转换成为可能。本文将详细介绍R Excel文件的概念、应用场景以及操作方法。 一、R Excel文件的概念…...
数据库(MySQL):使用命令从零开始在Navicat创建一个数据库及其数据表(一).创建基础表
一. 使用工具和命令 1.1 使用的工具 Navicat Premium 17 :“Navicat”是一套可创建多个连接的数据库管理工具。 MySQL版本8.0.39 。 1.2 使用的命令 Navicat中使用的命令 命令 命令解释 SHOW DATABASES; 展示所有的数据库 CREATE DATABASE 数据…...
电力通信物联网应用,国密网关守护电力数据安全
电力国密网关是用于保护电力调度数据网路由器和电力系统的局域网之间通信安全的电力专用网关机,主要为上下级控制系统之间的广域网通信提供认证与加密服务,实现数据传输的机密性、完整性。 国密算法网关功能特点 身份认证:对接入的设备和用户…...
vue:vite 代理服务器 proxy 配置
Vite 代理服务器(Proxy)的配置通常用于开发环境,以解决跨域请求等问题。以下是一个详细的配置步骤: 通过以上步骤,你就可以在 Vite 项目中配置代理服务器,以便在开发过程中方便地访问后端服务。 找到 Vi…...
Java【网络原理】(2)初识网络续与网络编程
目录 1.前言 2.正文 2.1TCP协议与UDP协议 2.2socket API进行网络编程 2.2.1DatagramPacket类 2.2.1.1发送数据报 2.2.1.2接收数据报 2.2.1.3获取数据报内容 2.2.1.4设置数据报内容 2.2.2DatagramSocket类 2.2.2.1构造方法 2.2.2.2常用方法 2.2.3具体代码与解释 3…...
AI+集装箱号码识别技术,主要发展方向和应用潜力
集装箱号码识别技术作为物流数字化的重要工具,其应用前景随着全球供应链的智能化升级和绿色转型需求不断扩大。结合当前技术发展和行业实践,以下是其未来的主要发展方向和应用潜力: 1.物流与港口智能化管理 自动化识别与效率提升࿱…...
安装可视化jar包部署平台JarManage
一、下载 下载地址:JarManage 发行版 - Gitee.com 🚒 下载 最新发行版 下载zip的里面linux和windows版本都有 二、运行 上传到服务器,解压进入目录 🚚 执行java -jar jarmanage-depoly.jar 命令运行 java -jar jarmanage-dep…...
后端之JPA(EntityGraph+JsonView)
不同表之间的级联操作或者说关联查询是很多业务场景都会用到的。 对于这种需求最朴素的方法自然是手动写关联表,然后对被关联的表也是手动插入数据。但是手写容易最后写成一堆shit代码,而且修改起来也是非常麻烦的。 学会使用现成的工具还是非常有利的…...
Java数据结构第十三期:走进二叉树的奇妙世界(二)
专栏:数据结构(Java版) 个人主页:手握风云 目录 一、二叉树的遍历 1.1. 前序遍历 1.2. 中序遍历 1.3. 后序遍历 1.4. 完整代码 二、二叉树的基本操作 2.1. 获取树中结点个数 2.1. 获取叶子结点个数 2.3. 获取第k层结点的个数 2.4. 获取二叉树的…...
JavaScript系列(86)--现代构建工具详解
JavaScript 现代构建工具详解 🔨 现代前端开发离不开构建工具,它们帮助我们处理模块打包、代码转换、资源优化等任务。让我们深入了解主流的构建工具及其应用。 构建工具概述 🌟 💡 小知识:构建工具主要解决代码转换…...
docker容器网络配置及常用操作
Linux内核实现名称空间的创建 ip netns(网络名称空间)命令 可以借助ip netns命令来完成对 Network Namespace 的各种操作。ip netns命令来自于iproute安装包,一般系统会默认安装,如果没有的话,请自行安装。 注意&am…...
Docker 性能优化指南
Docker 提供了强大的容器化功能,能够帮助开发者在不同的环境中构建、测试和部署应用。然而,随着容器化应用的不断增长,Docker 容器可能会面临一些性能瓶颈,影响其运行效率、资源占用和扩展能力。为了确保容器在生产环境中的高效运…...
课程1. 深度学习简介
课程1. 深度学习简介 神经网络结构逻辑回归XOR问题(异或问题) 中间特征的生成全连接神经网络中间网络层的激活函数Sigmoid函数Tanh函数ReLU函数其它激活函数 使用全连接神经网络解决 XOR 问题神经网络用于回归问题训练神经网络 不同类型的神经网络 附加材…...
【cuda学习日记】4.3 结构体数组与数组结构体
4.3 数组结构体(AoS)和结构体数组(SoA) AoS方法进行存储 struct innerStruct{float x;float y; };struct innerStruct myAOS[N];SoA方法来存储数据 struct innerArray{float x[N];float y[N]; };struct innerArray moa;如图说明…...
2025最新高维多目标优化:基于城市场景下无人机三维路径规划的导航变量的多目标粒子群优化算法(NMOPSO),MATLAB代码
一、基于导航变量的多目标粒子群优化算法(NMOPSO)介绍 基于导航变量的多目标粒子群优化算法(Navigation variable-based multi-objective particle swarm optimization,NMOPSO)是2025年提出的一种用于无人机路径规划的…...
数字IC后端设计实现OCC(On-chip Clock Controller)电路介绍及时钟树综合案例
数字IC后端时钟树综合专题(OCC电路案例分享) 复杂时钟设计时钟树综合(clock tree synthesis)常见20个典型案例 1、什么是OCC? 片上时钟控制器(On-chip Clock Controllers ,OCC),也称为扫描时钟控制器(Scan Clock Con…...
Linux内核,slub分配流程
我们根据上面的流程图,依次看下slub是如何分配的 首先从kmem_cache_cpu中分配,如果没有则从kmem_cache_cpu的partial链表分配,如果还没有则从kmem_cache_node中分配,如果kmem_cache_node中也没有,则需要向伙伴系统申请…...
本地部署DeepSeek-R1(Ollama+Docker+OpenWebUI知识库)
安装Ollama 打开 Ollama官网 https://ollama.com/下载安装 Ollama服务默认只允许本机访问,修改允许其它主机访问 OLLAMA_HOST0.0.0.0 ollama serve也可以添加系统环境变量 都知道模型体积很大,顺便也通过环境变量修改模型存放位置,我这…...
Java 实现快速排序算法:一条快速通道,分而治之
大家好,今天我们来聊聊快速排序(QuickSort)算法,这个经典的排序算法被广泛应用于各种需要高效排序的场景。作为一种分治法(Divide and Conquer)算法,快速排序的效率在平均情况下非常高ÿ…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
