【数据结构】排序算法（一）——冒泡排序

【背景】

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

【源码运行环境】

操作系统：Windows 10

编译环境：Dev C++(基于C99标准)

【基本思想】

两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止

【动态图解】

【源码实现】

/*
*方法名：swap
*作用：交换数组两个位置的元素 
*参数：待查找数组 array; 起始位置 i ; 结束位置 j; 
*返回值：void
*Author: WellLee
*最后一次修改时间：2018年12月6日 22:18:55 
*/
void swap(int array[], int i, int j)
{
	int temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}
/*
*方法名：BubbleSort 
*作用：冒泡排序粗暴版 
*参数：待查找数组 array; 数组长度length; 
*返回值：void
*Author: WellLee
*最后一次修改时间：2018年12月6日 22:18:55 
*/
void BubbleSort(int array[], int length)
{
	int i,j;
	for(i = 1; i < length; i++)
	{
		for(j = length - 1 ; j >= i; j--)
		{
			if(array[j] > array[j+1]){
				swap(array,j,j+1);
			}
		}
	} 
}
/*
*方法名：BubbleSort_2
*作用：冒泡排序优化版 
*参数：待查找数组 array; 数组长度length; 
*返回值：void
*Author: WellLee
*最后一次修改时间：2018年12月6日 22:18:55 
*/
void BubbleSort_2(int array[],int length)
{
	int i,j;
	int flag = 1;
	for(i = 1; i < length && flag == 1; i++)
	{
		flag = 0;
		for(j = length -1; j >= i; j--)
		{
			if(array[j] > array[j+1])
			{
				swap(array,j,j+1);
				flag = 1;
			}
		}
	}
}

【分析】

冒泡排序最好的情况就是表本身有序，那么根据改进版的代码此时的比较次数为( n – 1) 次比较，没有数据交换，时间复杂度为O(n)；当最坏的情况，即待排序表逆序，此时需要比较\(\begin{align} \sum_{i=2}^{n} (i -1 ) = 1+2 + 3 + \cdots + (n-1) = \frac{n(n-1)}{2} \end{align}\) 次，并作等数量级别的记录移动，为此总的时间复杂度为\( O(n^2)\);

【参考文献】

• 《大话数据结构》.程杰.清华大学出版社