十大排序之:冒泡排序

目录

一、简介

实现过程 

时间复杂度

二、代码实现

函数声明

Swap函数 

单趟

多趟

测试 

优化 


一、简介

冒泡排序是一种简单的排序算法,它重复地比较相邻的两个元素,如果顺序错误就交换它们,直到没有元素需要交换为止。这个过程类似于气泡在水中上升的过程,因此被称为冒泡排序。

 

实现过程 

下面是冒泡排序的实现过程:

  1. 从待排序的数组中的第一个元素开始,依次比较相邻的两个元素。
  2. 如果前一个元素大于后一个元素,则交换它们的位置。
  3. 继续比较下一对相邻元素,直到比较到数组的最后一个元素。
  4. 重复以上步骤,每次比较的元素个数减少一位,直到最后一个元素。
  5. 重复以上步骤,直到所有元素都按照从小到大的顺序排列。

时间复杂度

 冒泡排序的时间复杂度是O(n^2),其中n是待排序数组的长度。由于每次排序都会比较相邻的两个元素,因此需要进行n-1次比较。而每次比较都有可能进行元素交换,最坏情况下需要进行n-1次交换。因此,总的比较和交换次数都是(n-1)+(n-2)+(n-3)+...+1 = n*(n-1)/2(等差数列求和公式),即O(n^2)。

 

二、代码实现

思想随易,实现不易,接下来是冒泡排序的代码实现(以C语言为例)。

函数声明

void BubbleSort(int* a, int n);//接收一个数组,作为参数

 

Swap函数 

冒泡排序是一种交换排序,每次比较两个数,如果符合条件(大泡泡在前,小泡泡在后),则会发生位置的交换。我们先实现一个能完成两个数交换的函数Swap

Swap
功能:能实现两个数的交换
void Swap(int* pa, int* pb)
{int tmp = *pa;*pa = *pb;*pb = tmp;
}

 

单趟

我们先来完成一趟冒泡排序过程的代码:

假设有10个数,下标为0~9,在第一趟冒泡排序的过程中,要比较的下标为(0,1),(1,2),(2,3),... (8,9)。我们用for循环产生每对下标的前一个(或后一个)(以前一个为例),记为i,那么i的最大下标为n-2(n为数组元素个数)。因此,控制循环结束的条件为i<n-1(或i<=n-2)。

void BubbleSort(int* a, int n)
{//单趟(第一趟)排序的过程for (int i = 0; i < n - 1; i++){//前一个泡泡大,则换到后一个位置if (a[i] > a[i + 1]){Swap(&a[i], &a[i + 1]);}}
}

多趟

但是,以上的一趟排序只是把最大的数换到了最后,只解决了一个数的排序。因此,我们需要进行多趟的排序。假设有10(n)个数,我们只需要进行9(n-1)趟的排序,9个数到了他们正确的位置,那么余下的一个数也找到了他的位置。把趟数用j作为标记,把循环次数控制为n-1

void BubbleSort(int* a, int n)
{//j为趟数for (int j = 0; j < n - 1; j++){//单趟排序(第一趟)的过程for (int i = 0; i < n - 1; i++){//前一个泡泡大,则换到后一个位置if (a[i] > a[i + 1]){Swap(&a[i], &a[i + 1]);}}}
}

 0~n-2,循环次数为n-1。

那么,我们把第一趟的单趟冒泡排序走完后,完成了一个数的排序,把最大的数,放在了n-1,数组中最后一个下标的位置。接下来,第二趟的排序,我们要完成的是n-1个数的排序,最后一个位置的坐标为n-2,最后完成比较的那一对坐标为(n-3, n-2),所以i最大为n-3。单趟排序的代码需做些修改,使第j趟的排序,与i能够对应上。

void BubbleSort(int* a, int n)
{for (int j = 0; j < n - 1; j++){//单趟排序(第j趟)的过程for (int i = 0; i < n - 1 - j; i++){if (a[i] > a[i + 1]){Swap(&a[i], &a[i + 1]);}}}
}

我们把i控制为 i < n-1-j:

第一趟:j = 0,i < n-1-0,即 i < n - 1, i最大为n-2。

第二趟:j = 1,i < n-1-1,即 i < n - 2, i最大为n-3。

。。。

符合条件!

测试 

以上,就完成了冒泡排序的代码。

做些小小的测试:

执行完BubbleSort后,数组变为了有序,成功!

优化 

最后给出一个优化版本:

//冒泡
void BubbleSort(int* a, int n)
{for (int j = 0; j < n - 1; j++){//假设数组已经有序int flag = 1;//单趟排序(第j趟)的过程for (int i = 0; i < n - 1 - j; i++){if (a[i] > a[i + 1]){Swap(&a[i], &a[i + 1]);flag = 0;//数据发生了交换,假设错误}}//这趟排序无任何数据发生交换,数组已然有序if (flag == 1){break;}}
}

冒泡排序如果在进行某趟排序后,就已经有序了,我们再进行一趟排序后,发现无任何数据发生交换,就不然其进行下一趟的排序,直接跳出循环。 

 

以上为冒泡排序内容介绍,感谢各位读者三连支持!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1537816.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

风力发电叶片缺陷检测数据集

风力发电叶片缺陷检测数据集】nc: 4 names: [Burn Mark, Coating_defects, Crack, EROSION ] 名称&#xff1a;【烧伤痕迹, 涂层缺陷, 裂缝&#xff0c;侵蚀】共1095张&#xff0c;8:1:1比例划分&#xff0c;&#xff08;train;876张&#xff0c;val&#xff1a;109张&#xff…

AG32 MCU采集的数据如何通过内部AHB总线传输到FPGA逻辑

AG32 因为管脚可以灵活定义&#xff0c;可以硬件兼容STM32F407等器件&#xff0c;深受客户的喜爱和欢迎。并且AG32内置FPGA逻辑&#xff0c;可以帮助客户实现高速的数据处理&#xff0c;这是其他普通MCU无法比拟的。客户刚上手开发&#xff0c;沟通了一些技术上的疑问&#xff…

设计模式 组合模式(Composite Pattern)

组合模式简绍 组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许你将对象组合成树形结构来表示“部分-整体”的层次结构。组合模式使得客户端可以用一致的方式处理单个对象和组合对象。这样&#xff0c;可以在不知道对象具体类型的条…

【Python百日进阶-Web开发-FastAPI】Day801 - FastAPI是什么

文章目录 一、官网二、FastAPI是什么三、FastAPI特性3.1 基于开放标准3.2 自动生成文档3.3 更主流的 Python3.4 编辑器支持3.5 简洁3.6 验证3.7 安全性及身份验证3.8 依赖注入3.9 无限制"插件"3.10 测试四、Starlette 特性五、Pydantic 特性六、Python 类型提示简介6…

数据结构—队列

队列 概念 只允许在一端进行插入数据的操作&#xff0c;在另一端进行删除数据操作的特殊线性表&#xff0c;队列具有先进先出FIFO(First In First Out)。 入队列&#xff1a;进行插入操作的一端称为队尾。 出队列&#xff1a;进行删除操作的一端称为队头。 结构 队列也可以数组…

【前端】prop传值的用法

prop配置项的作用是让组件接收外部传过来的值。 组件标签上传值给vue组件对象 <script> export default {name: HelloWorld,data(){return{ }},props:[name,age] #简单接收 } </script>方式2:利用对象方式设置数据类型进行类型限制 props:{name:String…

《探索云原生与相关技术》

在当今的科技领域中&#xff0c;云原生&#xff08;Cloud Native&#xff09;已经成为了一个热门的话题。它代表着一种构建和运行应用程序的全新方式。 云原生的概念 云原生是一套技术体系和方法论&#xff0c;旨在充分利用云计算的优势来构建更具弹性、可扩展性和高效性的应…

开源 AI 智能名片与微信拓客小程序:基于人性洞察的内容营销新策略

摘要&#xff1a;本文分析了刷屏社交事件所呈现出的特征以及背后反映出的碎片时代人们的行为特点。通过引入网络人格三角形模型&#xff0c;探讨了人性特征在内容营销中的应用。结合开源 AI 智能名片与微信拓客小程序&#xff0c;提出了利用人性特点进行内容设计和传播规划的策…

2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】

目录 数据结构王道第2章之顺序表 顺序表的定义和基本操作 定义&#xff1a; 基本操作&#xff1a; 基本操作&#xff1a; ​编辑 顺序表的实现-静态分配​编辑 顺序表的静态分配初始化 如果“数组”存满了怎么办&#xff1a; 顺序表的实现-动态分配&#xff1a; ​编辑 顺序表…

java日志框架之JUL(Logging)

文章目录 一、JUL简介1、JUL组件介绍 二、Logger快速入门三、Logger日志级别1、日志级别2、默认级别info3、原理分析4、自定义日志级别5、日志持久化&#xff08;保存到磁盘&#xff09; 三、Logger父子关系四、Logger配置文件 一、JUL简介 JUL全程Java Util Logging&#xff…

【复刻】数字化转型是否促进了企业内共同富裕? —来自中国 A 股 (2002-2022年)

【顶刊复刻】数字化转型是否促进了企业内共同富裕?———来自中国 A 股上市公司的证据&#xff08;2002-2022&#xff09; 一、数据简介 本数据参考方明月等&#xff08;2023&#xff09;的研究方法&#xff0c;对原文数据进行了年份扩充&#xff0c;更新到了2003-2022年。并…

【例题】lanqiao4425 咖啡馆订单系统

样例输入 3 2 2 1 3 1 2样例输出 3 2样例说明 输入的数组为&#xff1a;【3&#xff0c;1&#xff0c;2】 增量序列为&#xff1a;【2&#xff0c;1】 当增量 h2&#xff1a;对于每一个索引 i&#xff0c;我们会将数组元素 arr[i] 与 arr[i−h] 进行比较&#xff0c;并进行可…

Qt构建JSON及解析JSON

目录 一.JSON简介 JSON对象 JSON数组 二.Qt中JSON介绍 QJsonvalue Qt中JSON对象 Qt中JSON数组 QJsonDocument 三.Qt构建JSON数组 四.解析JSON数组 一.JSON简介 一般来讲C类和对象在java中是无法直接直接使用的&#xff0c;因为压根就不是一个规则。但是他们在内存中…

我一进门就看见 AI 在啪啪啪狂敲代码

不知道小伙伴们有没有关注到最近又有一个超级火热的 AI 工具&#xff0c;叫做 Cursor AI。 松哥体验了一把&#xff0c;感觉以后能从画页面的桎梏中解脱出来了。 松哥来和小伙伴们演示一下这个工具的玩法。 一 Cursor IDE Cursor 是一款集成了 AI 编程辅助功能的新型 IDE&a…

探索 Python 的火焰:Fire 库的神秘力量

文章目录 &#x1f525; 探索 Python 的火焰&#xff1a;Fire 库的神秘力量第一部分&#xff1a;背景介绍第二部分&#xff1a;Fire 库是什么&#xff1f;第三部分&#xff1a;如何安装 Fire&#xff1f;第四部分&#xff1a;简单库函数使用方法第五部分&#xff1a;场景应用第…

NASA:ATLAS/ICESat-2 L3 A陆地冰高度,版本6

目录 简介 代码 引用 网址推荐 0代码在线构建地图应用 机器学习 ATLAS/ICESat-2 L3A Land Ice Height V006 ATLAS/ICESat-2 L3 A陆地冰高度&#xff0c;版本6 简介 该数据集&#xff08;ATL06&#xff09;提供了地理定位的陆冰表面高度&#xff08;WGS 84椭球面之上&a…

react hooks--useContext

概述 ◼ 在之前的开发中&#xff0c;我们要在组件中使用共享的Context有两种方式&#xff1a;  类组件可以通过 类名.contextType MyContext方式&#xff0c;在类中获取context&#xff1b; 多个Context或者在函数式组件中通过 MyContext.Consumer 方式共享context&…

ThreadX源码:Cortex-A7的tx_thread_irq_nesting_start(嵌套中断开始动作).s汇编代码分析

0 参考资料 Cortex M3权威指南(中文).pdf&#xff08;可以参考ARM指令集用法&#xff09; 1 前言 tx_thread_irq_nesting_start.s是用来实现Cortex-A7 IRQ嵌套中断的开始函数实现的汇编文件。 2 源码分析 源码如下&#xff1a; &#xff11;  IRQ_DISABLE 0x80…

文本多语言 AI 摘要 API 数据接口

文本多语言 AI 摘要 API 数据接口 文本 / 文本摘要 AI 生成文本摘要 AI 处理 / 智能摘要。 1. 产品功能 支持多语言摘要生成&#xff1b;支持长文本处理&#xff1b;基于 AI 模型&#xff0c;持续迭代优化&#xff1b;不存储 PDF 文件&#xff0c;处理完即释放&#xff0c;保…

讲个故事5.0

一、DORL的输入 1.1 训练集 训练集共有两个&#xff0c;分别为dataset_train和train_collector。dataset_train用于训练用户模型&#xff0c;即训练论文图6中的GPM&#xff0c;该训练过程有验证集无测试集&#xff1b;train_collector用于学习策略&#xff0c;即学习论文图6中…