八大算法排序@冒泡排序(C语言版本)

冒泡排序

概念

  冒泡排序(Bubble Sort)是一种简单直观的排序算法,它重复地遍历待排序序列,一次比较两个相邻的元素,如果它们的顺序错误就将它们交换过来。通过多次的遍历,使得最大的元素逐渐移动到待排序序列的最后,从而实现排序。



算法思想

  主要思路就是比较两个相邻的元素大小,如果顺序错误(与要实现的排序对比而言),则将两个元素交换位置。迭代比对下去,比完一趟后,实现最大的数移动到最后(升序)或最小的数移动到最后(降序),将数组的序列长度减1。
  按照以上的步骤,进行多趟的排序,最终实现数组的排序。我们那实现升序的一趟冒泡排序来进行模拟演变。



示例

如下是数组arr1 = { 6 , 4 , 3 , 9 , 2 , 1 , 5 , 7 , 8 }初始状态下的图文演示:

在这里插入图片描述
变量i存放未排序的第一个元素下标,end存放着数组的个数,数组最后一个元素的下标为end-1。



第一步:

第一步
比较下标 i 和 i+1 相邻两个元素的大小。arr1[i] < arr[i+1]。交换元素的顺序,然后对变量 i 自加1,迭代下去进行下一对的比较。



第二步:

第二步
比较下标 i 和 i+1 相邻两个元素的大小。arr1[i] < arr[i+1]。交换元素的顺序,然后变量 i 自加1,迭代下去进行下一对的比较。


迭代过程就是重复以上的动作。下面是后序的全部过程,如下:
在这里插入图片描述
  第一趟冒泡排序完后,数组中最大的元素9已经被移动到最后,此时对end减1。end从原来的9变为了8。end-1 “指向” 的是下标7。此时可以数组划分为了两个序列,一个是排好序的(下标为8的元素);另一个序列式未排好序的(下标为0 ~ 7的元素)。
(整个数组分为两个序列,前序列是未排好序的,后序列是排好序的。)


一趟冒泡排序排好一个元素,数组中还剩8个未排序的元素,那么只需要再执行七趟冒泡排序,最后当变量 i + 1 等于 end-1 时,判断是否交换arr1[i] 和 arr[i+1],然后整个数组排序完成。最后一个不用排,肯定就是在最左端。




算法实现



// 冒泡排序
void BubbleSort(int* a, int n)
{
	// 实现代码1
	int end = n;
	// 执行n-1趟冒泡排序
	while (end-1)
	{
		// 一趟冒泡排序的实现
		for (int i = 0; i < end - 1; i++)
		{
			if (a[i] > a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
			}
		}
		end--;
	}

	 实现代码2
	//for (int i = 0; i < n-1; i++)
	//{
	//	for (int j = 0; j < n - 1 -i; j++)
	//	{
	//		if (a[j] > a[j + 1])
	//		{
	//			Swap(&a[j], &a[j + 1]);
	//		}
	//	}
	//}

}





时间复杂度

O(N^2)。

计算过程为:

(考虑最坏的情况,如对逆序的数组进行升序的排序)
移动第一个元素时,需要挪动n-1次;
移动第二个元素时,需要挪动n-2次;
...
移动第n-1个元素时,需要挪动1次;
移动第n个元素时,需要挪动0次。

挪动的次数是一个公差为1的等差数列,对该数列求和,根据等差数列的前n项和公式求得
Sn=n^2/2;
即时间复杂度为O(n^2/2),又因为时间复杂度不计入系数的。
所以时间复杂度为O(n^2)


空间复杂度

O(1)。

因为是在原数组上进行排序的,没有用到多余的空间,所以空间复杂度为O(1)。




特性总结

1、 冒泡排序是一种非常容易理解的排序
2.、时间复杂度:O(N^2)
3.、空间复杂度:O(1)
4.、稳定性:稳定

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Windows—常用DOS命令

解释&#xff1a;DOS命令即面向磁盘的操作命令 进入DOS页面&#xff1a;快捷键“winR”&#xff0c;输入cmd help命令 help 【命令名】可查看其他命令的解释&#xff0c;直接输入help也可以查看部分命令 另外&#xff0c;如果输入help显示help不是内部或外部命令&#xff0c;…

ACCESS从零入门教程

最近&#xff0c;在公司实习自学了一款简单的access数据库软件&#xff0c;下面是自己的一些学习心得过程&#xff0c;供大家参考。 一、access导入数据 两种方法&#xff1a; 1、直接复制&#xff0c;crtl-c/v即可 2、若数据量较大&#xff0c;可以从access内部进行导入&am…

c++语言基础18-开房门

题目描述 假设你手里有一串钥匙&#xff0c;这串钥匙上每把钥匙都有一个编号&#xff0c;对应着一个房门的编号。现给你一个房门编号&#xff0c;你需要判断是否能够打开该房门。 输入描述 测试数据共有多组。 第一行为一个整数 s&#xff0c;表示共有多少组测试数据。 每组第一…

c# OpenCvSharp透视矫正参数调整器

透视矫正不够智能化&#xff0c;每次都要进行局部参数调整&#xff0c;不便于程序使用&#xff0c;程序流程还是那几个步骤&#xff1b; 1、读取图像、灰度化 2、高斯滤波 3、二值化 4、边缘检测 灰度化图 上个图看看经过调整透视矫正边缘检测结果我还是挺满意的 发现一个…

基于springboot智慧食堂管理系统源码和论文

随着Internet的发展&#xff0c;人们的日常生活已经离不开网络。未来人们的生活与工作将变得越来越数字化&#xff0c;网络化和电子化。网上管理&#xff0c;它将是直接管理“智慧食堂”系统的最新形式。本论文是以构建“智慧食堂”系统为目标&#xff0c;使用java技术制作&…

Java Synchronized 和 ReentrantLock

目录 介绍 synchronized synchronized 修饰实例方法 修饰静态类方法 synchronized 修饰代码块 实现细节 ReentrantLock ReentrantLock 基本使用 公平锁实现 读写锁&#xff08;ReentrantReadWriteLock&#xff09; 1. 创建读写锁对象&#xff1a; 2. 通过读写锁对象…

IDS 和 IPS:了解异同

IDS 和 IPS 是至关重要的网络安全技术&#xff0c;经常被混淆或互换使用。那么&#xff0c;IDS 和 IPS 之间有什么区别&#xff0c;哪一种是最适合您组织需求的选择呢&#xff1f; 什么是IDS&#xff08;入侵检测系统&#xff09;&#xff1f; 入侵检测系统 (IDS) 是一种网络…

【管理篇 / 登录】❀ 06. macOS下使用USB配置线登录 ❀ FortiGate 防火墙

【简介】飞塔防火墙上都会配有CONSOLE接口&#xff0c;包装里都会配置一根USB配置线&#xff0c;通过这个接口和这根线&#xff0c;我们可以用命令的方式登录飞塔防火墙进行操作。随着苹果电脑的普及&#xff0c;我们来学习一下&#xff0c;如果在MAC OS中用配置线登录飞塔防火…

【零基础入门TypeScript】判断条件和循环

目录 定环 无限循环 示例&#xff1a;while 与 do..while 中断语句 句法 流程图 例子 继续语句 句法 流程图 例子 输出 无限循环 语法&#xff1a;使用 for 循环的无限循环 示例&#xff1a;使用 for 循环的无限循环 语法&#xff1a;使用 while 循环进行无限循…

pytorch06:权重初始化

目录 一、梯度消失和梯度爆炸1.1相关概念1.2 代码实现1.3 实验结果1.4 方差计算1.5 标准差计算1.6 控制网络层输出标准差为11.7 带有激活函数的权重初始化 二、Xavier方法与Kaiming方法2.1 Xavier初始化2.2 Kaiming初始化2.3 常见的初始化方法 三、nn.init.calculate_gain 一、…

程序媛的mac修炼手册--MacOS系统更新升级史

啊&#xff0c;我这个口罩三年从未感染过新冠的天选免疫王&#xff0c;却被支原体击倒&#x1f637;大意了&#xff0c;前几天去医院体检&#xff0c;刚检查完出医院就摘口罩了&#x1f926;大伙儿还是要注意戴口罩&#xff0c;保重身体啊&#xff01;身体欠恙&#xff0c;就闲…

Excel 插件:ASAP Utilities Crack

ASAP Utilities是一款功能强大的 Excel 插件&#xff0c;填补了 Excel 的空白。在过去的 20 年里&#xff0c;我们的加载项已经发展成为世界上最受欢迎的 Microsoft Excel 加载项之一。 ASAP Utilities 中的功能数量&#xff08;300 多个&#xff09;可能看起来有点令人眼花缭乱…

Navicat 技术干货 | 聚合查询的介绍

基础 SQL 查询可以检索、插入、更新和删除记录&#xff0c;而聚合查询可通过提供求和、平均值或最大/最小值等的大型结果集&#xff0c;将数据库交互提升到一个新的水平。本文中&#xff0c;我们将探索聚合 SQL 查询的基础知识&#xff0c;并研究如何有效的利用他们来分析和汇总…

Unity中URP下的线性雾

文章目录 前言一、线性雾 雾效因子二、MixFog1、ComputeFogIntensity 雾效强度计算2、雾效颜色混合 lerp(fogColor, fragColor, fogIntensity); 前言 在之前的文章中&#xff0c;我们实现了URP下的雾效支持。 Unity中URP下的添加雾效支持 在上一篇文章中,我们解析了 URP 下统…

HCIA-Datacom题库(自己整理分类的)——其他网络协议【完】

&#xff08;一&#xff09;单选 下列属于链路状态协议的是? Direct static FTP OSPF 解析&#xff1a; FTP&#xff1a;文件传输协议 OSPF&#xff1a;链路状态路由协议 如下图所示的网络主机A通过Telnet登录到路由器A然后在远程的界面通过FTP获取路由器的配置文件&…

【已解决】Invalid bound statement (not found)

报错讯息 org.apache.ibatis.binding.BindingException: Invalid bound statement (not found): com.casey.mapper.SysRoleMapper.getUserRoleCode at org.apache.ibatis.binding.MapperMethod S q l C o m m a n d . < i n i t > ( M a p p e r M e t h o d . j a v a :…

iec104和iec61850

iec104和iec61850 IEC104 规约详细解读(一) 协议结构 IEC104 规约详细解读(二)交互流程以及协议解析 61850开发知识总结与分享【1】 Get the necesarry projects next to each other in the same directory; $ git clone https://github.com/robidev/iec61850_open_server.g…

【GoLang入门教程】Go语言几种标准库介绍(四)

编程语言的未来&#xff1f; 文章目录 编程语言的未来&#xff1f;前言几种库fmt库 (格式化操作)关键函数&#xff1a;示例 Go库标准库第三方库示例 html库(HTML 转义及模板系统)主要功能&#xff1a;示例 总结专栏集锦写在最后 前言 上一篇&#xff0c;我们介绍了debug、enco…

Vue2 - diff 原理(动图演示)

目录 1&#xff0c;diffdiff 的时间点 2&#xff0c;_update 函数3&#xff0c;_patch 函数&#xff08;进行 diff&#xff09;3.1&#xff0c;根节点比较3.2&#xff0c;子节点比较 4&#xff0c;key的问题举例1举例2 1&#xff0c;diff 解释&#xff1a;对比新旧虚拟DOM树&a…

很实用的ChatGPT网站—在线编程模块增补篇

很实用的ChatGPT网站&#xff08;http://chat-zh.com/&#xff09;——增补篇 今天介绍一个好兄弟开发的ChatGPT网站&#xff0c;网址[http://chat-zh.com/]。这个网站功能模块很多&#xff0c;包含生活、学习、医疗、法律、经济等很多方面。今天跟大家分享一下&#xff0c;新…