数据结构从入门到精通——冒泡排序

冒泡排序

  • 前言
  • 一、冒泡排序的基本思想
  • 二、冒泡排序的特性总结
  • 三、冒泡排序的动画演示
  • 四、冒泡排序的具体代码
    • test.c


前言

冒泡排序是一种简单的排序算法,通过重复遍历待排序数列,比较相邻元素的大小并交换位置,使得每一轮遍历后最大(或最小)的元素都会“冒泡”到数列的一端,直到整个数列有序。这种算法的时间复杂度较高,但在处理小规模数据或近乎有序的数据时表现良好,除此之外,与其他排序算法相比,冒泡排序更适用于教学而不适应于实际生活


一、冒泡排序的基本思想

在这里插入图片描述
冒泡排序的基本思想是通过相邻元素之间的比较和交换,使得每一趟排序过程中,最大(或最小)的元素能够“冒泡”到序列的一端,从而达到排序的目的。

具体来说,冒泡排序的算法过程可以分为以下几个步骤:

  1. 从序列的第一个元素开始,比较相邻的两个元素,如果它们的顺序错误(即前一个元素大于后一个元素),则交换这两个元素的位置。
  2. 接着,从序列的第二个元素开始,重复上述步骤,直到序列的最后一个元素。这样,第一趟排序结束后,最大的元素就会被放到序列的最后面。
  3. 接下来,对序列的前n-1个元素进行同样的操作,直到整个序列都有序为止。在每一趟排序过程中,都会有一个最大(或最小)的元素被放到序列的末尾。

冒泡排序的时间复杂度为O(n^2),其中n为序列的长度。虽然它的效率不如一些更高级的排序算法,但由于其实现简单,易于理解,因此在一些实际应用中仍然被广泛使用。

例如,在一些小型数据集的排序中,冒泡排序可以作为一种简单有效的解决方案。此外,在一些需要稳定排序的场合中,冒泡排序也是一种不错的选择,因为它在交换相邻元素时不会改变相等元素的相对顺序。但是像上述这些情况生活中出现的概率很小,没有人会为了冒泡排序而专门设置一串代码。

总之,冒泡排序虽然不是最优的排序算法,但它的基本思想简单易懂,具有教学意义,不适用于实际生活。

二、冒泡排序的特性总结

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

冒泡排序,作为一种基础的排序算法,虽然在实际应用中由于其效率问题较少被直接使用,但在理解排序算法的基本原理和特性上,它起到了至关重要的作用。以下是对冒泡排序特性的总结:

  1. 稳定性:冒泡排序是一种稳定的排序算法。这意味着在排序过程中,对于相等的元素,它们的相对顺序不会发生改变。这对于某些需要保持原有数据结构中元素间关系的场景来说是非常重要的。

  2. 简单易懂:冒泡排序的实现逻辑相对直观,容易理解。它通过相邻元素之间的比较和交换来逐步将最大值或最小值“冒泡”到序列的一端。

  3. 效率问题:尽管冒泡排序在理解上较为简单,但其效率并不高。它的时间复杂度在最坏情况下为O(n^2),其中n为待排序序列的长度。这意味着对于大型数据集,冒泡排序可能不是最优的选择。

  4. 优化空间:尽管基本冒泡排序效率不高,但可以通过一些优化手段来改进其性能。例如,可以设置一个标志位来跟踪在一次完整的遍历过程中是否发生了交换,如果没有发生交换,则说明序列已经有序,可以提前结束排序。

  5. 适应性:冒泡排序适用于小规模数据集或者部分有序的序列。对于部分有序的序列,冒泡排序的效率会相对较高,因为其可以在较少的遍历次数内完成排序。

综上所述,冒泡排序虽然在实际应用中可能不是最优的选择,但它在教学、理解排序算法原理以及处理小规模数据集或特定场景(如稳定性要求高的场景)下仍然具有重要意义。通过深入理解冒泡排序的特性,我们可以更好地掌握排序算法的基本原理和优化方法,为处理更复杂的数据结构和算法问题打下坚实的基础。

三、冒泡排序的动画演示

冒泡排序

冒泡排序的动画演示展示了冒泡排序算法的工作过程。在演示中,可以看到一系列数字按照顺序逐个比较和交换位置,直到所有数字按照升序或降序排列。通过动画,可以清晰地看到每个步骤中数字的变化,从而理解冒泡排序算法的原理和步骤。这种演示方式有助于学习者更好地掌握冒泡排序算法,并理解其在实际应用中的工作原理。

四、冒泡排序的具体代码

test.c

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void BubbleSort(int* a, int n);
void PrintArray(int* a, int n);
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void TestBubbleSort()
{
	//int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	PrintArray(a, sizeof(a) / sizeof(int));

	BubbleSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));
}


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int exchange = 0;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j + 1] <= a[j])
			{
				Swap(&a[j + 1], &a[j]);
				exchange = 1;
			}
		}
		if (exchange == 0)break;
	}
}
void TestOP()
{
	srand(time(0));
	const int N = 10000;
	int* a1 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
	}
	int begin1 = clock();
	BubbleSort(a1, N);
	int end1 = clock();
	printf("BubbleSort:%d\n", end1 - begin1);

	free(a1);
}

int main()
{
	TestBubbleSort();
	TestOP();

	return 0;
}

这段代码实现了冒泡排序算法。冒泡排序的基本思想是通过相邻元素的比较和交换来将大的元素逐步“冒泡”到最后。

代码中的函数BubbleSort接受两个参数,一个是待排序数组a,另一个是数组的长度n。

首先,外层的循环i表示排序的轮数,每一轮会把当前未排序部分的最大元素冒泡到最后。循环的终止条件是i < n - 1,因为最后一个元素无需再进行比较。

内层的循环j用来进行相邻元素的比较和交换。每一轮的比较从数组的第一个元素开始,依次比较相邻的两个元素。如果后一个元素小于等于前一个元素,就交换它们的位置。

在每一轮的内层循环结束后,通过exchange变量来判断是否有元素发生了交换。如果没有发生交换,说明数组已经是有序的,就可以提前结束排序。

最终,当外层的循环结束后,整个数组就按照从小到大的顺序排列好了。
在这里插入图片描述


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

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

相关文章

蓝桥杯 2023 省A 更小的数

主要思路&#xff1a; 输入一个长度为n的字符串&#xff0c;用二维数组dp[i][j]来记录子串[i, j]是否需要反转一次才能满足条件。使用动态规划自底向上地填充dp数组。根据问题的要求&#xff0c;需要考虑字符串的子串中字符的大小关系来判断是否需要反转。最后统计满足条件的子…

小红书,已破!支持无水印批量下载

在我们刷小红书时&#xff0c;经常会遇到自己喜欢的头像/壁纸/背景图图片或各大博主发布的视频教程&#xff0c;想保存下载使用和后续的查看&#xff0c;但保存下载后发现图片或视频右下角保留小红书的水印&#xff0c;很影响使用查看的体验。 所以本期文章最软库给大家分享一…

3D高斯泼溅的崛起

沉浸式媒体领域正在以前所未有的速度发展&#xff0c;其中 3D 高斯溅射成为一项关键突破。 这项技术在广泛的应用中看起来非常有前景&#xff0c;并且可能会彻底改变我们未来创建数字环境以及与数字环境交互的方式。 在本文中&#xff0c;我们将通过与摄影测量和 NeRF 等前辈进…

JAVA_会话

会话技术 1.会话: 一次会话包含多次请求和响应 2.功能: 在一次会话的范围内的多次请求&#xff0c;共享数据 3.方式: 3.1.客户端会话技术 Cookie(甜点) 1.概念: 客户端会话技术,将数据保存到客户端 2.快速入门: 1.创建Cookie对象,绑定数据new Cookie(String name,String v…

3000+人使用,这套人力资源数据分析工具还能这么用

中国科学院自动化研究所&#xff08;以下简称“自动化所”&#xff09;成立于1956年&#xff0c;是中国科学院率先布局成立的“人工智能创新研究院”的总体牵头单位&#xff0c;是中国最早开展智能科学与技术基础理论、关键技术和创新性应用研究的科研机构&#xff0c;也是中国…

G1和ZGC垃圾回收器学习

前言 ​ 随着JDK17的占有率不断升高和SpringBoot3最低支持JDk17&#xff0c;JDK17很大概率会成为大家后续升级的一个选择&#xff0c;而JDK17上最重要的垃圾回收器G1和ZGC&#xff0c;也就显得格外重要。大家提前了解或者学习一下肯定是有用的。 ​ 本篇文章也默认大家了解一…

Python 全栈体系【四阶】(十五)

第五章 深度学习 一、基本理论 1. 深度学习概述 1.1 引入 1.1.1 人工智能划时代事件 2016 年 3 月&#xff0c;Google 公司研发的 AlphaGo 以 4:1 击败世界围棋顶级选手李世石。次年&#xff0c;AlphaGo2.0 对战世界最年轻的围棋四冠王柯洁&#xff0c;以 3:0 击败对方。背后…

PCB板的叠构剖析及实际案例

PCB板可以有不同的层叠结构&#xff0c;具体取决于电路设计的要求和应用的复杂性。 以下是一些常见的PCB板叠构&#xff0c;包括单层、双层和多层PCB&#xff1a; 单层PCB&#xff08;Single-Layer PCB&#xff09;&#xff1a; 基本结构&#xff1a; 单层PCB由一个绝缘性基板组…

sqllab第二十八关通关笔记(附带28a)

知识点&#xff1a; union select 整体过滤 union all select 替换where id(输入)空格 过滤了&#xff0c;使用%09代替 经过不断的测试&#xff0c;发现原始语句为 where id(输入) 构造payload:id1)and%091(1 成功回显出了相关的信息 好&#xff0c;尝试进行错误注入 构造…

理解树的结构-算法通关村

理解树的结构-算法通关村 1.树的结构 树是一个有n个有限节点组成一个具有层次关系的集合&#xff0c;每个节点有0个或者多个子节点&#xff0c;没有父节点的节点称为根节点&#xff0c;也就是说除了根节点以外每个节点都有父节点&#xff0c;并且有且只有一个。树的种类比较多…

如何自定义异常类

如何自定义异常类 为什么要使用自定义异常类&#xff1f; 在 Java 中&#xff0c;自定义异常是指用户根据自己的需求创建的异常类。Java 提供了一些预定义的异常类&#xff0c;如 NullPointerException、ArrayIndexOutOfBoundsException 等&#xff0c;但有时这些预定义的异常…

直播预告!5位大厂测开学长学姐助力你上岸测开

大家好&#xff0c;我是洋子&#xff0c;24届春招补录&25届暑期实习招聘已经进入到白热化阶段&#xff0c;近期收到了很多同学关于求职问题的咨询&#xff0c;所以开一场公益直播来为大家答疑解惑 主题&#xff1a;校招测试开发求职如何准备&职业发展 时间&#xff1…

十二、MySQL 主从复制+高可用+读写分离

目录 一、mysqlkeeplived实现高可用LVS负载均衡 一、什么是高可用 二、为什么要用高可用 三、高可用的作用 四、keeplived 是什么&#xff1f;它用在哪里 五、安装mysql以及配置主从 六、keepalived安装 1、配置 单VIP 实现高可用 master上配置 2、backup上的配置 3、…

蓝桥杯-礼物-二分查找

题目 思路 --刚开始想到暴力尝试的方法&#xff0c;但是N太大了&#xff0c;第一个测试点都超时。题目中说前k个石头的和还有后k个石头的和要小于s&#xff0c;在这里要能想到开一个数组来求前n个石头的总重&#xff0c;然后求前k个的直接将sum[i]-sum[i-k-1]就行了&#xff0…

@EnableConfigurationProperties注解使用

前言 当我们想把配置的内容,动态赋值到某个配置类上的时候,可以使用EnableConfigurationProperties ConfigurationProperties注解 代码准备 创建配置文件prop.properties nameada age18 email123qq.com 创建配置类 ComponentScan("com.test.pops") PropertySo…

天地一体化5G网络中LNA的辐射效应

Youssouf A S, Habaebi M H, Hasbullah N F. The radiation effect on low noise amplifier implemented in the space-aerial–terrestrial integrated 5G networks[J]. IEEE Access, 2021, 9: 46641-46651. 图2 面向卫星的5G综合网络架构方案 这篇论文《The Radiation Effect…

docker快速安装达梦数据库

docker快速安装达梦数据库 文章目录 docker快速安装达梦数据库前言环境准备下载镜像运行、配置容器 前言 因为公司需要将自己的底代码平台与客户的需求做适配&#xff0c;客户要求必须满足信创要求&#xff0c;使用达梦数据库。所以需要将原有的MySQL数据库与达梦数据库适配&a…

Android:adb命令

执行adb命令的窗口如下 Mac或Linux系统里的终端窗口&#xff1b; window系统运行输入cmd打开的指令窗口&#xff1b; Android Studio 里控制下面的Terminal窗口 1. 查看已链接的设备和模拟器 adb devices -l 2. 查看Android内核版本号 adb shell getprop ro.build.version.re…

面试笔记——Redis(集群方案:主从复制、哨兵模式和分片集群)

主从复制 在 Redis 主从集群中&#xff0c;一个主节点&#xff08;Master&#xff09;负责处理客户端的读写请求&#xff0c;而多个从节点&#xff08;Slave&#xff09;则负责复制主节点的数据&#xff0c;并对外提供读取服务——解决高并发问题。 主节点&#xff08;Master&…

vue@2.7.16 使用less、less-loader

遇到问题&#xff0c;npm install less-loader7.3.0 --save安装好less-loader后&#xff0c;执行npm run serve 项目运行不起来&#xff0c;排查后发现在安装less-loader后就提示需要安装less&#xff0c;正确的安装应如下&#xff1a; npm install less less-loader7.3.0 --sa…