冒泡排序笔记

• 时间复杂度

  冒泡排序的平均时间复杂度 $O(n^2)$

  最好的情况下时间复杂度是 $O(n)$ ------ 基本有序的情况

  最坏的情况下时间复杂度是 $O(n^2)$ ------ 逆序的情况

• 空间复杂度 $O(n)$

• 稳定性----稳定的

冒泡的核心代码

for(int i=1;i<=n-1;i++)
	{
		for(int j=1;j<=n-i;j++)
		{
			if(a[j]>a[j+1])
			{
				swap(a[j],a[j+1]);
			}	
		}
	}

冒泡的优化核心代码

for(int i=1;i<=n-1;i++)
	{
		bool flag = true;
		for(int j=1;j<=n-i;j++)
		{
			if(a[j]>a[j+1])
			{
				swap(a[j],a[j+1]);
				flag = false;
			}	
		}
		if(flag) break;
	}

冒泡排序的动画演示(https://visualgo.net/en/sorting)