算法笔记--冒泡排序

冒泡排序是一种选择排序，算法简单，在数据基本有序的情况下效率较高。

1. 算法思想

          通过无序区中元素相邻元素的比较和交换，使最小的元素如同气泡一般浮动至顶端。

2. 时间复杂度

          最好情况 O(n)：序列正序有序，外循环只执行一次，内层比较n次，不需移动元素（针对改进版而言）

          最坏情况 O(n^2)：序列逆序有序，每次比较都需交换两个元素

3. 空间复杂度 O(1)

          就地排序，辅助空间为常数级

4. 稳定性

          稳定。元素的交换都是相邻交换，不改变同值元素的原始顺序

5. 代码实现（C语言）

          在基本版的基础上增加了一个记录当前有序位置的标志flag，以提高元素基本有序情况下的效率。

void BubbleSort(int *A, int n)
{
	int i, j;
	int flag, tmp;

	i = 0;
	while (i < n)
	{
		flag = n;

		for (j = n - 1; j > i; --j)
		{
			if (A[j] < A[j - 1])
			{
				flag = j - 1;
				tmp = A[j];
				A[j] = A[j - 1];
				A[j - 1] = tmp;
			}
		}

		i = flag;
	}
}