冒泡排序深入具体解释

冒泡排序深入具体解释

大家好,又见面了,我是全栈君。

冒泡排序的基本思想

冒泡排序(Bubble Sort)是一种交换排序,它的基本思想是:两两比較相邻记录的keyword,假设凡需则交换。直到没有凡需的记录位置。

一、冒泡排序简单实现(0基础版)

#include "stdafx.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status; 

#define MAXSIZE 10000  /* 用于要排序数组个数最大值。可依据须要改动 */
typedef struct
{
	int r[MAXSIZE+1];	/* 用于存储要排序数组,r[0]用作哨兵或暂时变量 */
	int length;			/* 用于记录顺序表的长度 */
}SqList;

void print(SqList L)
{
	int i;
	for(i=1;i<L.length;i++)
		printf("%d,",L.r[i]);
	printf("%d",L.r[i]);
	printf("\n");
}

/* 交换L中数组r的下标为i和j的值 */
void swap(SqList *L,int i,int j) 
{ 
	int temp=L->r[i]; 
	L->r[i]=L->r[j]; 
	L->r[j]=temp; 
}

/* 对顺序表L作交换排序(冒泡排序0基础版) */
void BubbleSort0(SqList *L)
{ 
	int i,j;
	for(i=1;i<L->length;i++)
	{
		for(j=i+1;j<=L->length;j++)
		{
			if(L->r[i]>L->r[j])
			{
				swap(L,i,j);/* 交换L->r[i]与L->r[j]的值 */
			}
		}
	}
}

#define  N 9
int _tmain(int argc, _TCHAR* argv[])
{
	int d[N]={9,1,5,8,3,7,4,6,2};
	SqList L0;
	int i;
	for(i=0;i<N;i++)
		L0.r[i+1]=d[i];
	L0.length=N;

	printf("排序前:\n");
	print(L0);

	BubbleSort0(&L0);
	printf("排序后:\n");
	print(L0);

	getchar();
	return 0;
}

执行结果:

冒泡排序深入具体解释

排序思想:依次实现前一个和后一个的比較,每次仅仅将最小的移至最高,其他元素位置差点儿不变。

冒泡排序深入具体解释

缺点:能够看出,在排好1和2的位置后,其余keyword的排序没有帮助(数字3反而还被换到了最后一位)。也就是说这个算法的效率是很低的。

二:正宗的冒泡排序

/* 对顺序表L作冒泡排序 */
void BubbleSort(SqList *L)
{ 
	int i,j;
	for(i=1;i<L->length;i++)
	{
		for(j=L->length-1;j>=i;j--)  /* 注意j是从后往前循环 */
		{
			if(L->r[j]>L->r[j+1]) /* 若前者大于后者(注意这里与上一算法的差异)*/
			{
				swap(L,j,j+1);/* 交换L->r[j]与L->r[j+1]的值 */
			}
		}
	}
}

冒泡排序深入具体解释
冒泡排序深入具体解释

代码分析:在不断循环的过程中,除了将keyword1放到第一的位置,我们还将keyword2从第九位置提到了第三的位置,显然这一算法比前面的要有进步,在上十万条数据的排序过程中,这样的差异会体现出来。

图中较小的数字如同气泡般慢慢浮到上面。因此就将此算法命名为冒泡算法。

长处总结:1)将最小keyword1提至最高; 2)将第一次比較过的keyword2放在合适的位置附近。

三:冒泡排序升级版

/* 对顺序表L作改进冒泡算法 */
void BubbleSort2(SqList *L)
{ 
	int i,j;
	Status flag=TRUE;			/* flag用来作为标记 */
	for(i=1;i<L->length && flag;i++) /* 若flag为true说明有过数据交换,否则停止循环 */
	{
		flag=FALSE;				/* 初始为False */
		for(j=L->length-1;j>=i;j--)
		{
			if(L->r[j]>L->r[j+1])
			{
				 swap(L,j,j+1);	/* 交换L->r[j]与L->r[j+1]的值 */
				 flag=TRUE;		/* 假设有数据交换。则flag为true */
			}
		}
	}
}


冒泡排序深入具体解释

除了第一和第二的keyword须要交换外。别的都已经是正常的顺序。当i=1时。交换了2和1,此时序列已经有序。可是算法仍然不依不饶地将i=2到9以及每一个循环中的循环都运行了一遍。虽然并没有交换数据,可是之后的大量比較还是大大地多余了。

长处:减去在排序k次后,表已经有序时,兴许的无需比較。

4、冒泡排序复杂度分析

分析它的时间复杂度。当最好的情况,也就是要排序的表本身就是有序的,依据最后改进的代码。进行n-1次的比較,间复杂度为o(n)。当最坏的情况,待排序表是逆序,此时须要比較总的次数为冒泡排序深入具体解释,并作等数级的记录移动。因此。总的时间复杂度为o(n2)。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116082.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Three.js呈现3D效果机房–初步方案[通俗易懂]

    Three.js呈现3D效果机房–初步方案[通俗易懂]3D机房系统是最近用户的需求,通过相关了解最后使用Three.js,也发现最近有东西可以写出来分享:webGL可以让我们在canvas上实现3D效果。而three.js是一款webGL框架,由于其易用性被广泛应用Three.js是通过对WebGL接口的封装与简化而形成的一个易用的图形库分步实现3D效果初始化3D模型参数开始搭建场景初始化渲染器初始化摄像机创建场景灯光布置创建网格线

  • 怎么查看git的用户名和密码_git修改用户名密码命令

    怎么查看git的用户名和密码_git修改用户名密码命令转载自:https://www.cnblogs.com/xihailong/p/13354628.html一、查看查看用户名:gitconfiguser.name查看密码:gitconfiguser.password查看邮箱:gitconfiguser.email查看配置信息:$gitconfig–list二、修改修改用户名gitconfig–globaluser.name“xxxx(新的用户名)”修改密码gitconfig–globaluse

  • 电脑蓝屏错误代码0x000000ED_电脑蓝屏0*000000ed怎么解决

    电脑蓝屏错误代码0x000000ED_电脑蓝屏0*000000ed怎么解决电脑蓝屏的原因很多,不同的电脑蓝屏显示的代码不同,对应的解决方法也不同。最近就有网友说自己的电脑蓝屏代码0x000000ed怎么办,不知道0x000000ed是什么意思。今天小编就教下大家修复电脑蓝屏代码0x000000ed的解决方法。0x000000ed蓝屏原因:说明I/0子系统试图加载到引导卷时失败。一般因为不正常断电导致的硬盘故障,从而导致启动时不能正常加载。具体的解决方法如下:1、先开机按f8看能否进入安全模式,能够进入的话,打开运行/输入CMD,键入命令chkdsk/f/r回…

  • Cinemachine(一)VirtualCamera和Brain的简单介绍「建议收藏」

    Cinemachine(一)VirtualCamera和Brain的简单介绍「建议收藏」https://zhuanlan.zhihu.com/p/103584975简介Cinemachine是Unity在2017版本推出的一套处理Camera的组件。利用Cinemachine我们可以不通过敲代码就实现很多摄像机功能,例如目标跟随,镜头切换等等。官方文档:https://docs.unity3d.com/Packages/com.unity.cinemachine@2.6/manual/index.html我们可以通过PackageManager来安装C…

  • 下载mysql驱动jar包

    下载mysql驱动jar包MYSQL官网历史驱动Jar包下载地址:https://downloads.mysql.com/archives/c-j/ProductVersion选择mysql版本,OperatingSystem选择PlatformIndepen,然后下载即可

  • python长度单位换算表_长度单位换算表大全

    python长度单位换算表_长度单位换算表大全长度单位换算表大全我国传统的长度单位有里、丈、尺、寸等。1里=150丈=500米。2里=1公里(1000米)1丈=10尺,1尺=10寸。1丈=3.33米,1尺=3.33分米,1寸=3.33厘米。国际单位制中,长度的标准单位是“米”,用符号“m”表示。1960年第十一届国际计量大会:“米的长度等于氪-86原子的2P10和5d1能级之间跃迁的辐射在真空中波长的1650763.73倍”。其他的长度单位还…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号