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

排序算法——冒泡排序

排序算法是计算机科学中最基本的概念之一。在众多排序算法中,冒泡排序因其实现简单而被广泛学习。尽管它不是最高效的排序方法,但对于理解基本的排序概念非常有用。本文将深入探讨冒泡排序的原理、实现、优缺点以及应用场景。

1. 冒泡排序原理

冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。这个过程像气泡一样上浮到数列的顶端,因此得名“冒泡排序”。

算法步骤

  1. 比较相邻的元素:从数列的开始两个相邻元素开始,如果前一个比后一个大,就交换它们。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

2. 冒泡排序的代码实现

以下是冒泡排序的基本实现,使用C++编写:

在冒泡排序的每一轮遍历中,如果没有发生任何元素的交换,这意味着数组已经是完全排序的。这时,就没有继续进行后续遍历的必要,因为数组已处于排序状态。swapped 变量就是用来跟踪每轮遍历是否发生了交换。

通过swapped变量对基本的冒泡排序进行了改善,使冒泡排序在最优的情况下时间复杂度为O(n).

#include <vector>void bubbleSort(std::vector<int>& arr) {int n = arr.size();bool swapped;for (int i = 0; i < n-1; i++) {swapped = false;for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {std::swap(arr[j], arr[j+1]);swapped = true;}}if (!swapped)break;}
}

. 冒泡排序的复杂度分析

时间复杂度

  • 最佳情况:T(n) = O(n),当输入的数据已经是升序时。
  • 最差情况:T(n) = O(n²),当输入的数据是降序时。
  • 平均情况:T(n) = O(n²)。

空间复杂度

  • O(1),因为只需要常量级的额外空间。

4. 冒泡排序的优缺点

优点

  • 简单易懂:冒泡排序算法非常直观,容易实现。
  • 空间效率高:它是原地排序,不需要额外的存储空间。

缺点

  • 效率低:对于大数据集来说,冒泡排序的速度非常慢。
  • 多次交换:每次只移动相邻的两个元素,因此交换操作较多。

5. 应用场景

由于冒泡排序的效率较低,它通常不适用于数据量较大的场合。然而,对于小数据集或者是初学算法和编程的场景,冒泡排序是一个非常好的选择,它有助于新手理解排序的基本原理。

相关文章:

排序算法——冒泡排序

排序算法是计算机科学中最基本的概念之一。在众多排序算法中&#xff0c;冒泡排序因其实现简单而被广泛学习。尽管它不是最高效的排序方法&#xff0c;但对于理解基本的排序概念非常有用。本文将深入探讨冒泡排序的原理、实现、优缺点以及应用场景。 1. 冒泡排序原理 冒泡排序…...

边缘智能网关如何应对环境污染难题

随着我国工业化、城镇化的深入推进&#xff0c;包括大气污染在内的环境污染防治压力继续加大。为应对环境污染防治难题&#xff0c;佰马综合边缘计算、物联网、智能感知等技术&#xff0c;基于边缘智能网关打造环境污染实时监测、预警及智能干预方案&#xff0c;可应用于大气保…...

uniapp定时器的应用

1、初始化定时器 data(){return{timer: null, //定时器} } 2、定时器的使用 定时器分两种&#xff0c;setInterval和setTimeout。 二者的区别&#xff1a; setInterval函数会无限执行下去&#xff0c;除非调用clearInterval函数来停止它。setTimeout函数只执行一次&#x…...

Docker中安装Oracle10g和oracle增删改查

Docker中安装Oracle 10g 一、Docker中安装Oracle 10安装步骤二、连接数据库登录三 oracle数据库的增删改查及联表查询的相关操作oracle数据库,创建students数据表,创建100万条数据增删改查 一、Docker中安装Oracle 10安装步骤 Docker中安装Oracle 10g 1.下载镜像 docker pull …...

推荐算法:HNSW【推荐出与用户搜索的类似的/用户感兴趣的商品】

HNSW算法概述 HNSW&#xff08;Hierarchical Navigable Small Word&#xff09;算法算是目前推荐领域里面常用的ANN&#xff08;Approximate Nearest Neighbor&#xff09;算法了。其目的就是在极大量的候选集当中如何快速地找到一个query最近邻的k个元素。 要找到一个query的…...

C++ //例3.14 找出100~200间的全部素数。

C程序设计 &#xff08;第三版&#xff09; 谭浩强 例3.14 例3.14 找出100~200间的全部素数。 IDE工具&#xff1a;VS2010 Note: 使用不同的IDE工具可能有部分差异。 代码块 方法&#xff1a;使用函数的模块化设计 #include <iostream> #include <iomanip> #i…...

虚幻学习笔记11—C++结构体、枚举与蓝图的通信

一、前言 结构体的定义和枚举类似&#xff0c;枚举的定义有两种方式。区别是结构体必须以“F”开头命名&#xff0c;而枚举不用。 额外再讲了一下蓝图生成时暴露变量的方法。 二、实现 2.1、结构体 1、定义结构体 代码如下&#xff0c;注意这个定义的代码一定要在“UCLASS()”…...

【android开发-19】android中内容提供者contentProvider用法讲解

1&#xff0c;内容URI 在Android系统中&#xff0c;Content URI是一种用于唯一标识和访问应用程序中的数据的方法。它由Android系统提供&#xff0c;通过Content Provider来实现数据的共享和访问。 Content URI使用特定的格式来标识数据&#xff0c;通常以"content://&qu…...

浅谈排序——快速排序(最常用的排序)

快速排序&#xff08;Quick Sort&#xff09;是一种常见的排序算法&#xff0c;由英国计算机科学家东尼霍尔&#xff08;Tony Hoare&#xff09;在1960年发明。这是一种分治算法&#xff0c;基本思想是通过一趟排序将要排序的数据分割成独立的两部分&#xff0c;其中一部分的所…...

Springboot项目实现简单的文件服务器,实现文件上传+图片及文件回显

文章目录 写在前面一、配置1、application.properties2、webMvc配置3、查看效果 二、文件上传 写在前面 平常工作中的项目&#xff0c;上传的文件一般都会传到对象存储云服务中。当接手一个小项目&#xff0c;如何自己动手搭建一个文件服务器&#xff0c;实现图片、文件的回显…...

5V低压步进电机驱动芯片GC6150,应用于摄像机,机器人 医疗器械等产品中。具有低噪声、低振动的特点

GC6150是双通道5V低压步进电机驱动器&#xff0c;具有低噪声、低振动的特点&#xff0c;特别适用于相机变焦对焦系统、万向架、摇头机等精度、低噪声STM控制系统&#xff0c;该芯片为每个通道集成了一个256微步的驱动器。通过SPI & T2C接口&#xff0c;客户可以方使地调整驱…...

3D Web轻量引擎HOOPS Communicator如何实现对大模型的渲染支持?

除了读取轻松外&#xff0c;HOOPS Communicator对超大模型的支持效果也非常好&#xff0c;它可以支持30GB的包含70万个零件和3.5亿个三角面的Catia装配模型&#xff01; 那么它是如何来实现对大模型的支持呢&#xff1f; 我们将从以下几个方面与大家分享&#xff1a;最低帧率…...

『 Linux 』进程地址空间概念

文章目录 &#x1fad9; 前言&#x1fad9; 进程地址空间是什么&#x1fad9; 写时拷贝&#x1fad9; 可执行程序中的虚拟地址&#x1fad9; 物理地址分布方式 &#x1fad9; 前言 在c/C中存在一种内存的概念; 一般来说一个内存的空间分布包括栈区,堆区,代码段等等; 且内存是…...

PySpark大数据处理详细教程

欢迎各位数据爱好者&#xff01;今天&#xff0c;我很高兴与您分享我的最新博客&#xff0c;专注于探索 PySpark DataFrame 的强大功能。无论您是刚入门的数据分析师&#xff0c;还是寻求深入了解大数据技术的专业人士&#xff0c;这里都有丰富的知识和实用的技巧等着您。让我们…...

三(五)ts非基础类型(对象)

在ts里面定义对象的方式也有很多。 普通定义 let obj1:{} {} // obj1.name fufu 报错&#xff0c;只能定义为空对象且不能修改 // 但是可以在赋初始值的时候直接添加属性&#xff0c;这是ts在类型推断时&#xff0c;它会宽容地匹配对象的结构。 let obj2:{} {name: fufu}…...

HeartBeat监控Redis状态

目录 一、概述 二、 安装部署 三、配置 四、启动服务 五、查看数据 一、概述 使用heartbeat可以实现在kibana界面对redis服务存活状态进行观察&#xff0c;如有必要&#xff0c;也可在服务宕机后立即向相关人员发送邮件通知 二、 安装部署 参照文章&#xff1a;HeartBeat监…...

FairGuard无缝兼容小米澎湃OS、ColorOS 14 、鸿蒙4!

随着移动互联网时代的发展&#xff0c;各大手机厂商为打造生态系统、构建自身的技术壁垒&#xff0c;纷纷投身自研操作系统。 而对于一款游戏安全产品&#xff0c;在不同操作系统下&#xff0c;是否能够无缝兼容并且提供稳定的、高强度的加密保护&#xff0c;成了行业的一大痛…...

【Copilot】Edge浏览器的copilot消失了怎么办

这种原因&#xff0c;可能是因为你的ip地址的不在这个服务的允许范围内。你需要重新使用之前出现copilot的ip地址&#xff0c;然后退出edge的账号&#xff0c;重新登录一遍&#xff0c;最后重启edge&#xff0c;就能够使得copilot侧边栏重新出现了。...

C++入门【6-C++ 修饰符类型】

C 修饰符类型 C 允许在 char、int 和 double 数据类型前放置修饰符。 修饰符是用于改变变量类型的行为的关键字&#xff0c;它更能满足各种情境的需求。 下面列出了数据类型修饰符&#xff1a; signed&#xff1a;表示变量可以存储负数。对于整型变量来说&#xff0c;signe…...

STP笔记总结

STP --- 生成树协议 STP&#xff08;Spanning Tree Protocol&#xff0c;生成树协议&#xff09;是根据 IEEE802.1D标准建立的&#xff0c;用于在局域网中消除数据链路层环路的协议。运行STP协议的设备通过彼此交互信息发现网络中的环路&#xff0c;并有选择地对某些端口进行阻…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...