[排序篇] 冒泡排序

目录

一、概念

二、冒泡排序

2.1 冒泡降序(从大到小排序)

2.2 冒泡升序(从小到大排序)

三、冒泡排序应用 

总结 


一、概念

冒泡排序核心思想:每次比较两个相邻的元素,如果它们不符合排序规则(升序或降序)则把它们交换过来。

二、冒泡排序

2.1 冒泡降序(从大到小排序)

冒泡降序:每次比较相邻的两个数,如果后面的数比前面的数大,则交换这两个数的位置。 

假设将 12 18 76 35 99 这 5 个数进行从大到小的排序(即,越小的越靠后)

如上图所示,从左往右逐列看,5 个数总共需要遍历 4 次(即 n - 1 次);而每列从上往下逐行看,每遍历一次总共需要排序 n - i 次(i 代表遍历的次数)。

1. 首先看第一列: 

1.1 第一行:比较第 1 位和第 2 位的大小,发现 12 比 18 要小,因为是降序,所以需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 12 76 35 99;

1.2 第二行:比较第 2 位和第 3 位的大小,发现 12 比 76 要小,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 76 12 35 99;

1.3 第三行:比较第 3 位和第 4 位的大小,发现 12 比 35 要小,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 76 35 12 99;

1.4 第三行:比较第 4 位和第 5 位的大小,发现 12 比 99 要小,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 76 35 99 12; 

遍历第一次并经过 4 次排序后,5 个数中最小的一个 12 已经归位到队列的最后一位了(即第 5 位)。

2. 再看第二列: 

2.1 第一行:比较第 1 位和第 2 位的大小,发现 18 比 76 要小,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 76 18 35 99 12

2.2 第二行:比较第 2 位和第 3 位的大小,发现 18 比 35 要小,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 76 35 18 99 12

2.3 第三行:比较第 3 位和第 4 位的大小,发现 18 比 99 要小,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 76 35 99 18 12

遍历第二次并经过 3 次排序后,5 个数中倒数第二小的一个 18 已经归位到队列的倒数第二位了(即第 4 位)。 

3. 再看第三列: 

2.1 第一行:比较第 1 位和第 2 位的大小,发现 76 比 35 要大,则不需要交换这两个数的位置。并且这 5 个数的顺序仍然是 76 35 99 18 12

2.2 第二行:比较第 2 位和第 3 位的大小,发现 35 比 99 要小,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 76 99 35 18 12

遍历第三次并经过 2 次排序后,5 个数中倒数第三小的一个 35 已经归位到队列的倒数第三位了(即第 3 位)。  

3. 最后看第四列: 

2.1 第一行:比较第 1 位和第 2 位的大小,发现 76 比 99 要小,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 99 76 35 18 12

遍历第四次并经过 1 次排序后,5 个数中倒数第四小的一个 76 已经归位到队列的倒数第四位了(即第 2 位)。 

最后总结一下:如果有 n 个数进行排序,只需将 n-1 个数归位,也就是说要进行 n-1 次操作。而 “每一次” 都需要从第 1 位开始进行相邻两个数的比较,将较小的一个数放在后面,比较完毕后向后移一位继续比较下面两个相邻数的大小,重复此步骤,直到最后一个尚未归位的数,已经归位的数则无需再进行比较。

冒泡降序例程1(推荐): 

#include <stdio.h>

void main()
{
	int arr[5];
	int n;
	int tmp;

	scanf("%d", &n); //输入一个数n,表示接下来有n个数
	for (int i = 0; i < n; i++) //循环读入n个数到数组arr中
		scanf("%d", &arr[i]);
		
	//冒泡降序的核心代码
	for (int i = 1; i <= n - 1; i++) { //n个数排序,只需进行 n-1 次(i从1开始,因此i需要包含 n-1)
		for (int j = 0; j < n - i; j++) { //i从1开始,则j从第1位(数组0下标)开始与后面一个数比较,直到最后一个尚未归位的数(已归位的数无需再比较,因此只需排序 n-i 次)
			if (arr[j] < arr[j+1]) { //相邻两个数比较大小并交换
				tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
			}
		}
	}
	
	//输出结果
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

冒泡降序例程2: 

#include <stdio.h>

void main()
{
	int arr[5];
	int n;
	int tmp;

	scanf("%d", &n); //输入一个数n,表示接下来有n个数
	for (int i = 0; i < n; i++) //循环读入n个数到数组arr中
		scanf("%d", &arr[i]);
		
	//冒泡降序的核心代码
	for (int i = 0; i < n - 1; i++) { //n个数排序,只需进行 n-1 次(i从0开始,因此i不能包含 n-1)
		for (int j = 1; j < n - i; j++) { //i从0开始,则j从第2位(即数组1下标)开始与前面一个数比较,直到最后一个尚未归位的数(已归位的数无需再比较,因此只需排序 n-i 次)
			if (arr[j-1] < arr[j]) { //相邻两个数比较大小并交换
				tmp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = tmp;
			}
		}
	}
	
	//输出结果
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

冒泡降序例程3:  

#include <stdio.h>

void main()
{
	int arr[5];
	int n;
	int tmp;

	scanf("%d", &n); //输入一个数n,表示接下来有n个数
	for (int i = 0; i < n; i++) //循环读入n个数到数组arr中
		scanf("%d", &arr[i]);

	//冒泡降序的核心代码
	for (int i = 0; i < n - 1; i++) { //n个数排序,只需进行 n-1 次 (i从0开始,因此i不能包含 n-1)
		for (int j = 0; j < n - i - 1; j++) { //从第1位(数组0下标)开始与后面一个数比较,直到最后一个尚未归位的数(已归位的数无需再比较,然而i和j都是从0开始,因此只需排序 n-i-1 次)
			if (arr[j] < arr[j+1]) { //相邻两个数比较大小并交换
				tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
			}
		}
	}
	
	//输出结果
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

2.2 冒泡升序(从小到大排序)

冒泡升序:每次比较相邻的两个数,如果后面的数比前面的数小,则交换这两个数的位置。 

假设将 99 35 18 76 12 这 5 个数进行从小到大的排序(即,越大的越靠后)

如上图所示,从左往右逐列看,5 个数总共需要遍历 4 次(即 n - 1 次);而每列从上往下逐行看,每遍历一次总共需要排序 n - i 次(i 代表遍历的次数)。

1. 首先看第一列: 

1.1 第一行:比较第 1 位和第 2 位的大小,发现 99 比 35 要大,因为是升序,所以需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 99 18 76 12;

1.2 第二行:比较第 2 位和第 3 位的大小,发现 99 比 18 要大,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 18 99 76 12;

1.3 第三行:比较第 3 位和第 4 位的大小,发现 99 比 76 要大,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 18 76 99 12;

1.4 第三行:比较第 4 位和第 5 位的大小,发现 99 比 12 要大,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 18 76 12 99

遍历第一次并经过 4 次排序后,5 个数中最大的一个 99 已经归位到队列的最后一位了(即第 5 位)。

2. 再看第二列: 

2.1 第一行:比较第 1 位和第 2 位的大小,发现 35 比 18 要大,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 35 76 12 99

2.2 第二行:比较第 2 位和第 3 位的大小,发现 35 比 76 要小,则不需要交换这两个数的位置。并且这 5 个数的顺序仍然是 18 35 76 12 99

2.3 第三行:比较第 3 位和第 4 位的大小,发现 76 比 12 要大,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 35 12 76 99

遍历第二次并经过 3 次排序后,5 个数中第二大的一个 76 已经归位到队列的倒数第二位了(即第 4 位)。 

3. 再看第三列: 

2.1 第一行:比较第 1 位和第 2 位的大小,发现 18 比 35 要小,则不需要交换这两个数的位置。并且这 5 个数的顺序仍然是 18 35 12 76 99

2.2 第二行:比较第 2 位和第 3 位的大小,发现 35 比 12 要大,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 18 12 35 76 99

遍历第三次并经过 2 次排序后,5 个数中第三大的一个 35 已经归位到队列的倒数第三位了(即第 3 位)。  

3. 最后看第四列: 

2.1 第一行:比较第 1 位和第 2 位的大小,发现 18 比 12 要大,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 12 18 35 76 99

遍历第四次并经过 1 次排序后,5 个数中第四大的一个 18 已经归位到队列的倒数第四位了(即第 2 位)。 

最后总结一下:如果有 n 个数进行排序,只需将 n-1 个数归位,也就是说要进行 n-1 次操作。而 “每一次” 都需要从第 1 位开始进行相邻两个数的比较,将较大的一个数放在后面,比较完毕后向后移一位继续比较下面两个相邻数的大小,重复此步骤,直到最后一个尚未归位的数,已经归位的数则无需再进行比较。

冒泡升序例程1(推荐): 

#include <stdio.h>

void main()
{
	int arr[5];
	int n;
	int tmp;

	scanf("%d", &n); //输入一个数n,表示接下来有n个数
	for (int i = 0; i < n; i++) //循环读入n个数到数组arr中
		scanf("%d", &arr[i]);

	//冒泡降序的核心代码
	for (int i = 1; i <= n - 1; i++)) { //n个数排序,只需进行 n-1 次(i从1开始,因此i需要包含 n-1)
		for (int j = 0; j < n - i; j++) { //i从1开始,则j从第1位(数组0下标)开始与后面一个数比较,直到最后一个尚未归位的数(已归位的数无需再比较,因此只需排序 n-i 次)
			if (arr[j] > arr[j+1]) { //相邻两个数比较大小并交换
				tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
			}
		}
	}
	
	//输出结果
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

冒泡升序例程2:  

#include <stdio.h>

void main()
{
	int arr[5];
	int n;
	int tmp;

	scanf("%d", &n); //输入一个数n,表示接下来有n个数
	for (int i = 0; i < n; i++) //循环读入n个数到数组arr中
		scanf("%d", &arr[i]);
		
	//冒泡降序的核心代码
	for (int i = 0; i < n - 1; i++) { //n个数排序,只需进行 n-1 次(i从0开始,因此i不能包含 n-1)
		for (int j = 1; j < n - i; j++) { //i从0开始,则j从第2位(即数组1下标)开始与前面一个数比较,直到最后一个尚未归位的数(已归位的数无需再比较,因此只需排序 n-i 次)
			if (arr[j-1] > arr[j]) { //相邻两个数比较大小并交换
				tmp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = tmp;
			}
		}
	}
	
	//输出结果
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

冒泡升序例程3: 

#include <stdio.h>

void main()
{
	int arr[5];
	int n;
	int tmp;

	scanf("%d", &n); //输入一个数n,表示接下来有n个数
	for (int i = 0; i < n; i++) //循环读入n个数到数组arr中
		scanf("%d", &arr[i]);

	//冒泡降序的核心代码
	for (int i = 0; i < n - 1; i++) { //n个数排序,只需进行 n-1 次 (i从0开始,因此i不能包含 n-1)
		for (int j = 0; j < n - i - 1; j++) { //从第1位(数组0下标)开始与后面一个数比较,直到最后一个尚未归位的数(已归位的数无需再比较,然而i和j都是从0开始,因此只需排序 n-i-1 次)
			if (arr[j] > arr[j+1]) { //相邻两个数比较大小并交换
				tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
			}
		}
	}
	
	//输出结果
	for (int i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

三、冒泡排序应用 

假设一个班有 5 个学生,需要将这 5 个学生期末考试的分数,从高到低排序,并且输出对应的学生姓名和性别。大家可以思考一下,该如何实现?

根据 2.1 冒泡降序原理,在此,我们只需要声明一个结构体,其成员包含学生的姓名、性别和分数(假设满分为 100,并分数只有整数)。下面是实际的例子。

#include <stdio.h>

struct student {
	char name[24];
	char sex[8];
	int score;
};

void main()
{
	struct student stu[5];
	struct student tmp;
	int n;

	scanf("%d", &n); //输入班级总人数
	for (int i = 0; i < n; i++) //循环读入学生总数到数组stu中
		scanf("%s %s %d", stu[i].name, stu[i].sex, &stu[i].score);

	//开始对学生进行分数排序
	for (int i = 1; i <= n - 1; i++) {
		for (int j = 0; j < n - i; j++) {
			if (stu[j].score < stu[j+1].score) { //比较相邻的两个数,分数高的排前面
				tmp = stu[j];
				stu[j] = stu[j+1];
				stu[j+1] = tmp;
			}
		}
	}

	//输出结果
	for (int i = 0; i < n; i++)
		printf("%s %s %d", stu[i].name, stu[i].sex, &stu[i].score);
	printf("\n");
}

可以输入以下数据进行验证:

5

李文 男 80
韩飞 男 50
晓晓 女 86
胡峰 男 78
陈肖 女 66

运行结果是: 

晓晓 女 86

李文 男 80
胡峰 男 78
陈肖 女 66
韩飞 男 50

总结 

1. 冒泡降序:每次比较相邻的两个数,如果后面的数比前面数大,则交换这两个数的位置;

2. 冒泡升序:每次比较相邻的两个数,如果后面的数比前面数小,则交换这两个数的位置;

3. 从例程代码来看,可知冒泡排序有很多种方法,但是万变不离其宗,都是围绕 “如果有 n 个数进行排序,则需遍历 n-1 次,而 “每一次” 需要排序 n-i 次,并且都是从第 1 位开始进行相邻两个数的比较,将较小或较大的一个数放在后面,如此重复,直到最后一个尚未归位的数” 展开。

4. “冒泡降序” 与 “冒泡升序” 例程代码的唯一差异是:相邻的两个数较小或较大的放在后面。例如,if (arr[j] < arr[j+1]) 或 if (arr[j] > arr[j+1]);

5. 冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是 O(N^{2})。这是一个非常高的时间复杂度。正如 Donald E. Knuth 所说:“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外,似乎没有什么值得推荐的。”

那还有没有更好的排序算法呢?有,请看下章节——快速排序。

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

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

相关文章

Web自动化测试工具起到哪些重要作用

随着互联网的迅猛发展&#xff0c;Web应用程序已经成为企业不可或缺的一部分。为了确保Web应用的质量和可靠性&#xff0c;Web自动化测试工具变得至关重要。以下是Web自动化测试工具在软件开发生命周期中发挥的作用&#xff1a; 1. 提高测试效率和速度 Web自动化测试工具可以快…

【媒体开发】利用FFMPEG进行推拉流

1. 下载并启动媒体服务 MediaMTX&#xff0c;也即之前的rtsp-simple-server&#xff0c;是一个即用型、零依赖的实时媒体服务器和媒体代理&#xff0c;允许发布、读取、代理和记录视频和音频流。 从Releases bluenviron/mediamtx GitHub找到最新版&#xff0c;下载对应平台…

Web UI 自动化 元素定位利器

序 元素定位&#xff0c;对于 Web UI 自动化而言&#xff0c;绝对是大家成长道路上的一道绊脚石。 很多初学者&#xff0c;都“死”在了元素定位上&#xff0c;从而失去了学习的兴趣。导致职业规划不得不半途而废~ 那么&#xff0c;今天&#xff0c;我们就使用 Katalon Stu…

python实战演练之迎接冬至的第一场雪

写在前面 WINTER IS COMING Python实现大雪纷飞的效果&#xff0c;完整代码在文末哦~ 准备开始 WINTER IS COMING Python是一种高级编程语言&#xff0c;Turtle是Python的一个图形化模块&#xff0c;它可以帮助学习者更好地理解编程概念&#xff0c;同时可以进行图形化编程。 …

DS二叉排序树之删除

Description 给出一个数据序列&#xff0c;建立二叉排序树&#xff0c;并实现删除功能 对二叉排序树进行中序遍历&#xff0c;可以得到有序的数据序列 Input 第一行输入t&#xff0c;表示有t个数据序列 第二行输入n&#xff0c;表示首个序列包含n个数据 第三行输入n个数据…

修改汽车的控制系统实现自动驾驶,基于一个开源的汽车驾驶辅助系统实现全自动驾驶

修改汽车的控制系统实现自动驾驶,基于一个开源的汽车驾驶辅助系统实现全自动驾驶。 自动驾驶汽车依靠人工智能、视觉计算、雷达、监控装置和全球定位系统协同合作,让电脑可以在没有任何人类主动的操作下,自动安全地操作机动车辆。 演示视频: Openpilot :一个开源的汽车驾…

音乐制作工具 Ableton Live 12中文最新 for Mac

Ableton Live 12 Mac具有直观的界面和强大的功能&#xff0c;使得音乐制作变得更加简单和高效。它支持实时录制、编辑和混音&#xff0c;用户可以在创作过程中随时进行修改和调整。此外&#xff0c;该软件还提供了各种音频效果、虚拟乐器和采样器&#xff0c;使用户可以创建出更…

el-table的复选框占满全格

el-table的复选框格子很小每次点击都点不到&#xff0c;又不想设置行点击&#xff0c;因为每次复制内容都会选中&#xff0c;实现效果是点击el-table的复选框单元格就可以选中 <template><div style"width: 60vw; margin: 10px;"><el-table :data&quo…

1 CPU实现的基本框图

汇编语言 && 指令格式 CPU设计的框架&#xff1a;三级流水线 ROM存放指令和数据&#xff0c;大端模式&小端模式&#xff0c;地址对齐 取指 译码&#xff1a; 执行&#xff1a; 汇编语言 & 指令格式 流水线实现工作机制 模块功能划分&接口信号 参考…

新工科:数据科学与大数据技术实验中心解决方案,赋能高校新工科数智人才培养

随着数字经济蓬勃发展&#xff0c;数字化产业和产业数字化成为就业增长新动能。据人瑞人才与德勤调研显示&#xff0c;未来3年&#xff0c;数字产业化企业最需要运营人员和开发人员&#xff08;包括大数据开发工程师、数据建模开发工程师等&#xff09;&#xff0c;其次是数据分…

12 位多通道国产芯片ACM32F403/F433 系列,支持 MPU 存储保护功能,应用于工业控制,智能家居等产品中

ACM32F403/F433 芯片的内核基于 ARMv8-M 架构&#xff0c;支持 Cortex-M33 和 Cortex-M4F 指令集。芯片内核 支持一整套DSP指令用于数字信号处理&#xff0c;支持单精度FPU处理浮点数据&#xff0c;同时还支持Memory Protection Unit &#xff08;MPU&#xff09;用于提升应用的…

lv13 交叉开发环境搭建

1 ubuntu网络环境配置 目的&#xff1a;让Ubuntu可以上外网&#xff0c;让开发板可以与ubuntu互通 2 tftp 服务器环境搭建 tftp&#xff08;Trivial File Transfer Protocol&#xff09;即简单文件传输协议 是TCP/IP协议族中的一个用来在客户机与服务器之间进行简单文件 传输…

LabVIEW发开发电状态监测系统

LabVIEW发开发电状态监测系统 对发电设备的持续监测对于确保可靠的电力供应至消费者极为重要。它不仅能够及时提醒操作员注意发电设备的潜在损坏&#xff0c;还能减少由于设备故障造成的停机时间。为了达到这一目标&#xff0c;开发了一款基于LabVIEW的软件&#xff0c;专门用…

基于YOLOv8深度学习的血细胞检测与计数系统【python源码+Pyqt5界面+数据集+训练代码】目标检测、深度学习实战、智慧医疗

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…

【UE5】监控摄像头效果(下)

目录 效果 步骤 一、多摄像机视角切换 二、摄像头自动旋转巡视 三、摄像头跟踪拍摄 效果 步骤 一、多摄像机视角切换 1. 打开玩家控制器“MyPlayerController”&#xff0c;添加一个变量&#xff0c;命名为“BP_SecurityCameraArray”&#xff0c;类型为“BP_SecurityCa…

Word插件-好用的插件-批量插入图片-大珩助手

现有100张图片&#xff0c;需要批量插入word中&#xff0c;并在word中以每页6张图片的形式呈现&#xff0c;请问怎样做&#xff1f; 使用word大珩助手&#xff0c;多媒体-插入图片&#xff0c;根据图片的长宽&#xff0c;选择连续图片、一行2个图或一行3个图&#xff0c;可一次…

线程互斥与同步

用户级线程 内核的LWP Linux线程 OS概念中经常说的 用户级线程 和 内核级线程 也就是线程实现真的是在OS内部实现&#xff0c;还是应用层或用户层实现 很明显Linux是属于用户级线程 用户级执行流&#xff08;用户级线程&#xff09; &#xff1a;内核lwp 1 : 1 也有1&…

#define宏定义

#define 语法规定 #define定义标识符 语法: #define name stuff #define例子 #include<stdio.h> #define A 100 #define STR "abc" #define FOR for(;;)int main() {printf("%d\n", A);printf("%s\n", STR);FOR;return 0; } 运行结果…

Flutter实现自定义二级列表

在Flutter开发中&#xff0c;其实系统已经给我们提供了一个可靠的二级列表展开的API&#xff08;ExpansionPanelList&#xff09;&#xff0c;我们先看系统的二级列表展开效果&#xff0c;一次只能展开一个&#xff0c;用ExpansionPanelList.radio实现 由此可见&#xff0c;已经…

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

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