排序算法之二：冒泡排序

冒泡排序的思路

冒泡排序是交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

• 第一趟：将最大的值排到最后
• 第二趟：将次大的值排到倒二
• ......
• 第n-1趟：将最小的排到第一

冒泡排序动图：https://pic4.zhimg.com/v2-33a947c71ad62b254cab62e5364d2813_b.webp

由于冒泡排序的时候，大的沉地，小的浮上来，所以得名冒泡排序

冒泡排序的特性

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

代码示例

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
				Swap(&a[j - 1], &a[j]);
		}
	}
	/*for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j+1])
				Swap(&a[j], &a[j+1]);
		}
	}*/
}