欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排序算法系列2——冒泡排序

程序员文章站 2022-07-08 14:44:49
...

冒泡排序1.0

这是最容易理解的交换排序的思想,不是真正的冒泡排序,因为它不是利用两两比较临近数字的大小得出结果,而是拿要确定的位置的数字与后边各个数字相比较,确定大当家的位置就要让待选的大当家和后边的小喽啰都比试一番,谁赢了就换,二当家也是如此出来的,依次排列。比如对1,5,3,2,6进行从从小到大升序输出

那么第一轮就是比较1和5的大小,由于1<5,则1和5不用交换,然后再让1和3比较一直到和6比较,一轮下来,就可以保证第一个位置是最小的了

第二轮就从5开始,分别和后边的3,2,6进行比较,5先和3交换,3再和2交换,最后第二轮定下来前两个位置最小,以此类推

void BubbleSort1(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);
			}
		}
	}
}

 

排序算法系列2——冒泡排序

冒泡排序2.0

通过冒泡排序1.0我们不难发现,每次遍历一次数组只能从待排序的位置里找出一个确定值,而待排序的数互相之间并没有简单排序,造成资源浪费。真正的冒泡算法是两两比较临近数字的大小,每一次遍历待排序的数组都会由比较有简单的排序

比如1,5,3,2,6

第一轮

6和2比较,由于6比2大,所以不用交换1 5 3 2 6

2和3比较,2小,所以2和3交换 1 5 2 3 6

2和5比较,2小,所以2和5交换 1 2 5 3 6

2和1比较,2大,所以不用交换,此时这一趟遍历不仅将最小值放到了第一的位置,而且12,25,23之间也是有序的了

void BubbleSort2(SqList *L)
{
	int i,j;
	for(i=1;i<=L->length;i++)
	{
		for(j=L->length-1;j>=i;j--)  //相邻比较,从后往前冒泡,直到第一个泡一定是最小的
		{
			if(L->r[j+1]<L->r[j])
			{
				swap(L,j+1,j);
			}
		}
	}
}

排序算法系列2——冒泡排序

冒泡排序3.0(冒泡排序的优化)

冒泡排序2.0在待排序的数组已经有序的情况下,比如1,5,3,2,6在第二轮1 2 3 5 6就已经有序了,但是由于此时的i=2,还要进行i=3,i=4,i=5的情况下的没有必要的近邻比较,所以如果在i=3走完一轮后,若发现没有交换数字,即为已经有序,就停止循环好了

void BubbleSort3(SqList *L)
{
	int i=0,j;
	bool flag = true;
	for(i=1;i<=L->length&&flag;i++)
	{
		printf("\n%d",i);//打印i的值,查看循环了几次
		flag=false;
		for(j=L->length-1;j>=1;j--)  
		{
			if(L->r[j+1]<L->r[j])
			{
				swap(L,j,j+1);
				flag=true;
			}
		}
		
	}
}

 

从i值的打印情况可见,在第三轮的时候发现没有交换就结束遍历了

排序算法系列2——冒泡排序

测试程序:

int main()
{
	SqList L;
	CreateSq(L);
	//BubbleSort1(&L);
	//BubbleSort2(&L);
	BubbleSort3(&L);
	PrintSq(L);
}

冒泡排序复杂度分析:

最好的情况是已经有序的顺序表,需要有n-1此比较,0此交换,复杂度为O(n)

最坏的情况是逆序的情况,需要有1+2+3+...n-1此比较和移动,复杂度为O(n^2)