图解冒泡排序算法

举报
mindtechnist 发表于 2023/04/27 10:48:48 2023/04/27
【摘要】 ​目录冒泡排序算法分析冒泡算法的改进改进版冒泡排序代码实现冒泡排序时间复杂度分析冒泡排序算法分析冒泡排序:Bubble sort,也叫做起泡排序,是一种交换性质的排序,基本思想是相邻两条记录进行比较,不符合规则就交换,符合规则不交换。冒泡排序的具体步骤描述如下第一趟排序:第1个元素与第2个元素比较,如果第1个元素大于第2个元素则交换,否则不进行任何操作;第2个元素与第3个元素比较,如果第2个...

目录

冒泡排序算法分析

冒泡算法的改进

改进版冒泡排序代码实现

冒泡排序时间复杂度分析


冒泡排序算法分析

冒泡排序:Bubble sort,也叫做起泡排序,是一种交换性质的排序,基本思想是相邻两条记录进行比较,不符合规则就交换,符合规则不交换。冒泡排序的具体步骤描述如下

第一趟排序:

第1个元素与第2个元素比较,如果第1个元素大于第2个元素则交换,否则不进行任何操作;第2个元素与第3个元素比较,如果第2个元素大于第3个元素,则交换两个元素,否则不进行任何操作;重复上面操作,两两比较直到第n-1个元素和第n个元素比较完毕,第一趟冒泡结束。

编辑

经过第一趟排序后,整个数列中最大的数,通过冒泡冒到了数列的最后一个位置。

第二趟排序:

对前n-1个元素进行冒泡排序,即第1个位置与第2个位置比较,大于则交换,否则无操作;一直到第n-2个位置和第n-1个位置比较,大于则交换,否则无操作。通过第二趟冒泡排序,前n-1个元素中最大的数冒泡到n-1位置,也就是原始数组的倒数第二个位置(原始数组第二大的数)。

编辑

 第n-1趟排序:

 通过这种两两比较,经过n-1趟冒泡就可以将整个数组变为有序数组。并且从示意图中可以看出,红色的22本来就在黑色的22的前面,排序后红色22依然在黑色22前面,这说明冒泡排序不会改变相同数据原来的顺序,这说明,冒泡排序算法是稳定的。

冒泡算法的改进

有时候会有这样的情况,一组数据只有少数数据的顺序不对,而其他数据的顺序都是符合我们需要的顺序的(比如从小到大),比如下图中的情况

编辑

 这组数据只有前两个位置不符合从小到大的顺序,而后面三个数据都已经符合从小到大的顺序了。此时,只需要一趟排序就可以完成整个数组的排序

编辑

 但是,如果按照冒泡排序算法的全部流程,需要走完n-1趟排序才能完成,而第一趟冒泡排序之后的剩余流程其实是没有必要的。

这时,可以在冒泡排序中增加一个标志Flag,如果某一趟冒泡排序过程中,没有发生任何数据交换,则认为整个数组已经有序了,不需要在进行下一趟的冒泡排序,算法结束。比如上图中,在第一趟排序后整个数组已经从小到大排序完毕了,第二趟冒泡排序时,没有发生任何数据交换,则不再进行后续的冒泡,算法结束。这样就节省了很多不必要的时间,只需两趟冒泡就可以结束排序,而正常冒泡排序需要四趟冒泡。

改进版冒泡排序代码实现

//交换 i j 位置的元素
void swap(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}

//冒泡排序
void bubble_sort(int array[], int num) //数组做函数参数会退化为指针,所以要传入数组元素个数
{
	int i = 0, j = 0, ChangeFlag = 1;
	for (i = 0; (i < num - 1) && (ChangeFlag == 1); i++) //总共多少趟排序 num - 1
	{
		ChangeFlag = 0; //默认假设无数据交换
		for (j = num - 1; j > i; j--)
		{
			if (array[j] < array[j - 1])
			{
				swap(array, j, j - 1);
				ChangeFlag = 1;
			}
		}
	}
}

冒泡排序的时候,从后往前冒或者从前往后冒都是可以的,也就是代码中的j从num-1开始或者从1开始都可以。

冒泡排序时间复杂度分析

时间复杂度是衡量一个排序算法好坏的重要标志,特别是在大量数据排序的时候。对于冒泡排序算法,最好的情况下,经过一趟排序就可以完成排序,总共需要n-1次两两比较的操作,此时复杂度为O(n);最坏的情况下,需要n-1趟排序才能完成整个数组的排序,此时需要的操作次数为,第一趟冒泡n-1次交换,第二趟冒泡n-2次交换,直到第n-1趟排序1次交换结束,共需要

(n-1)+(n-2)+\cdot \cdot \cdot +2+1编辑

 次两两比较的操作,时间复杂度为O(n*n)。所以,冒泡排序的时间复杂度为O(n^{2})编辑

总结:冒泡排序是一种,稳定的,时间复杂度为O(n^{2})编辑的,简单的内排序。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。