Machine World | Math World

记录实验过程

【数据结构】排序算法(一)——冒泡排序

【背景】

冒泡排序(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)\);

【参考文献】

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

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注