C++中常用的十大排序方法之1——冒泡排序

embedded/2025/2/2 22:14:28/

 成长路上不孤单😊😊😊😊😊😊

【😊///计算机爱好者😊///持续分享所学😊///如有需要欢迎收藏转发///😊】

今日分享关于C++中常用的排序方法之——冒泡排序的相关内容!

关于【C++中常用的排序方法之——冒泡排序】

目录:

  • 一、 冒泡排序的定义
  • 二、冒泡排序的算法原理
  • 三、冒泡排序的算法示例
  • 四、冒泡排序的算法分析
  • 五、冒泡排序的特点
  • 六、冒泡排序的优点
  • 七、冒泡排序的缺点

冒泡排序(Bubble Sort)

一、冒泡排序的定义

冒泡排序的英文Bubble Sort,是一种最基础的交换排序。
大家一定都喝过汽水,汽水中常常有许多小小的气泡,哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻,所以小气泡可以一点一点向上浮动。而我们的冒泡排序之所以叫做冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。

  

二、冒泡排序的算法原理

假定序列中有n个数,要进行从小到大的排序。若参与排序的数组元素共有n个,则需要n-1轮排序。在第í轮排序中,从左端开始,相邻两数比较大小,若反序则将两者交换位置,直到比较第n+1-i个数为止。第1个数与第2个数比较,第2个数和第3个数比较,一直到第n-i个数与第n+1-i个数比较,一共处理 n-i次。此时,第n+1-i个位置上的数已经有序,后续就不需要参加以后的排序。 

(1)第1轮冒泡排序先从第1个数和第2个数开始比较,若第1个数大于第2个数,则需要交换两者的位置;否则保持不变。重复这一过程,直到处理完本轮数列中最后两个数。 

(2)第2轮冒泡排序与第1轮冒泡排序进行相同的排序,使大的数交换到n-2的位置上。 

(3)重复以上过程,共需经过n-1轮冒泡排序后,数据实现升序排序。

三、冒泡排序的算法示例

对于序列[26,28,24,11],采用非递减规则进行排序,排序过程如下所示。 

  

(1) 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 

(2) 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 

(3) 针对所有的元素重复以上的步骤,除了最后一个。 

(4) 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

四、冒泡排序的算法分析

1、时间复杂度

若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数

  

    

若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i 次,关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:

  

  

2、算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不会再交换的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法

五、冒泡排序的特点

 时间复杂度‌:冒泡排序的时间复杂度为O(n^2)。在最坏的情况下(即初始序列完全逆序),需要进行n(n-1)/2次比较和3n(n-1)/2次移动,时间复杂度为O(n^2)。在最好的情况下(即初始序列已经有序),时间复杂度为O(n),但这种情况较为罕见。

空间复杂度‌:冒泡排序是一种就地排序算法,不需要额外的存储空间,因此空间复杂度为O(1)。

稳定性‌:冒泡排序是一种稳定的排序算法,即相同元素的相对位置不会改变。

适用场景‌:由于冒泡排序的时间复杂度较高,它适用于数据量较小的情况。对于大量数据的排序,效率较低。

算法原理‌:冒泡排序通过重复遍历待排序的数列,比较两个相邻的元素,如果它们的顺序错误就交换过来。遍历工作是重复进行的,直到没有再需要交换的元素为止。

优化方法‌:可以通过设置一个标志位来优化冒泡排序。如果在一次完整的遍历中没有发生交换,说明数组已经有序,可以直接结束排序过程。这种方法可以在某些情况下将时间复杂度降低到O(n)。

六、冒泡排序优点

1‌、 实现简单‌:冒泡排序的算法逻辑非常简单,容易理解和实现。它只需要通过重复遍历要排序的数列,比较相邻元素的值,并在必要时交换它们的位置。

‌2、代码简洁‌:冒泡排序的代码非常简洁,不需要复杂的操作和额外的存储空间。

3‌、原地排序‌:冒泡排序是一种原地排序算法,不需要额外的内存空间来存储排序结果。它直接在原始数组上进行元素的比较和交换操作。

4‌、稳定性‌:冒泡排序是一种稳定的排序算法,即相等元素的相对顺序在排序前后保持不变。只有当两个相邻元素进行交换时才会改变它们的相对顺序。

5‌、适用于小规模数据‌:在数据规模较小的情况下,冒泡排序的性能还是可以接受的。对于小规模的数据集,冒泡排序可能比其他复杂的排序算法更快。

七、冒泡排序的缺点

 1、时间复杂度高‌:冒泡排序的时间复杂度为O(n^2),在数据量较大时效率较低,尤其是当数据完全逆序时,时间复杂度达到O(n^2)。

 2‌、不适合大规模数据‌:由于其较高的时间复杂度,冒泡排序不适合处理大规模数据集。 


http://www.ppmy.cn/embedded/159023.html

相关文章

【Unity2D 2022:C#Script】DoTween插件的使用

一、插件介绍 DOTween 是一个快速、高效、完全类型安全的 Unity 面向对象的动画引擎,针对 C# 用户进行了优化,免费和开源,具有大量高级功能 二、插件的下载 1. DoTween官网:DOTween (HOTween v2) 2. DoTween下载: …

Qt事件处理:理解处理器、过滤器与事件系统

1. 事件 事件 是一个描述应用程序中、发生的某些事情的对象。 在 Qt 中,所有事件都继承自 QEvent ,并且每个事件都有特定的标识符,如:Qt::MouseButtonPress 代表鼠标按下事件。 每个事件对象包含该事件的所有相关信息&#xff…

Keepalived高可用集群入门学习

一、高可用集群 1.LB:load Balance 负载均衡 HA:High Availability 高可用集群 HPC: High Performance Computing 高性能集群 2.提高系统高用性的解决方案:降低MTTR(mean time to repair)平均故障时间 建立冗余机制…

WGCLOUD服务器资源监控软件使用笔记 - Token is error是什么错误

[wgcloud-agent]2025/01/30 10:41:30 WgcloudAgent.go:90: 主机监控信息上报server开始 [wgcloud-agent]2025/01/30 10:41:30 WgcloudAgent.go:99: 主机监控信息上报server返回信息: {"result":"Token is error"} 这个错误是因为agent配置的wgToken和serv…

javaweb复习总结

Maven仓库的作用 Jar包管理编译、打包、测试 Maven仓库分类 本地仓库远程仓库 私服中央仓库其他公共库 Maven命令 mvn clean 刷新清理mvn clean compile 编译mvn clean test 执行所有测试用例mvn clean package 打包mvn clean install 下载jar包 Git工作流程: 从工…

【江苏省乡镇街道边界】面图层shp格式arcgis数据+乡镇名称和编码wgs84无偏移内容测评

江苏省乡镇界面图层shp格式arcgis数据乡镇名称和编码2020年wgs84坐标无偏移

Vue简介

目录 Vue是什么?为什么要使用Vue?Vue的三种加载方式拓展:什么是渐进式框架? Vue是什么? Vue是一套用于构建用户界面的渐进式 JavaScript (主张最少)框架 ,开发者只需关注视图层。另一方面,当与…

深入了解 npm 和 pnpm:前端包管理工具的选择与比较

在现代前端开发中,包管理工具已经成为了必不可少的组成部分。它们帮助我们管理项目的依赖、自动化任务、以及在团队协作时确保一致的开发环境。最常见的前端包管理工具有 npm 和 pnpm,它们各自具有独特的特点和优势。今天,我们就来一起深入了…