冒泡排序算法详解之C语言版

一、算法原理

冒泡排序是一种常用的排序算法，属于稳定排序法，其时间复杂度为O(n^2)。
冒泡排序法的原理就是从前向后依次比较相邻两个元素的大小，大元素后沉，类似于水中的泡泡逐步上浮的过程，随着泡泡逐渐接近水面，水中压强逐渐减小，水泡体积逐渐增大，因此成为冒泡排序。
冒泡排序法包括多趟排序过程，每一趟排序都是从数组的第一个元素开始，以步长为1的增量依次对相邻的两个元素进行比较大小，反序的话则交换此二元素。

Demo：
假设有数据如下表所示：数组记为data

第一趟排序：
从下标为1的元素开始，向后依次比较相邻元素大小。首先比较data[1]和data[2]，此时data[1] < data[2]，因此不用交换元素。

之后比较data[2]和data[3]的大小，此时数据反序，需要交换

接着比较data[3]和data[4]的大小，此时数据不需要交换。

之后比较data[4]和data[5]的大小，此时数据需要交换。至此完成了第一趟冒泡排序过程，把数组中的最大元素冒泡到了最后的位置。
仔细想想，像不像水中的水泡冒泡的过程。

第二趟排序：
和第一趟排序一样，仍旧从数组的第一个元素开始向后依次进行比较大小。但是由于经过第一趟排序之后，最大的元素已经到了最后的位置，因此第二趟排序就截止到数组的倒数第二个位置。

第三趟排序：

第四趟排序：

至此，该数组的冒泡排序结束。从上述演示过程可以看出，具有n个元素的数组使用冒泡排序法进行排序，需要进行n-1趟排序，每一趟排序都冒出剩余元素中的最大值，放到剩余元素的末尾。

二、冒泡排序算法流程图

三、冒泡排序算法之C程序

1.冒泡排序算法之C语言版

/*
功能：使用选择排序法对数组data进行排序
输入参数：
	data[]，已知数据散乱的数组
	n，元素的个数
输出参数：
	data[]，排好序的数组
返回值：无 
*/
void BubbleSort( int data[], int n )
{
	int i, j, k, t;
	for( i = 1; i <= n-1; i++ )
	{
		for( j = 1; j <= n-i; j++ )
		{
			if( data[j+1] < data[j] )
			{
				t         = data[j+1];
				data[j+1] = data[j];
				data[j]   = t;
			}
		}
	}
}

2.完整的代码（仅供参考）

#include"stdio.h"
#define MaxLength 100

int TotalNum = 0;
void InputData( int &count, int arrt[] );
void BubbleSort( int data[], int n );

int main()
{
	int count = 0, i, j;
	int data[MaxLength];
	InputData( count, data );
	printf( "排序前的数据：" );
	for( i = 1; i <= count; i++ )
	{
		printf( "%5d", data[i] );
	}
	printf( "\n" ); 
	BubbleSort( data, count ); 
	
	return 0;
} 
/*
功能：使用选择排序法对数组data进行排序
输入参数：
	data[]，已知数据散乱的数组
	n，元素的个数
输出参数：
	data[]，排好序的数组
返回值：无 
*/
void BubbleSort( int data[], int n )
{
	int i, j, k, t;
	for( i = 1; i <= n-1; i++ )
	{
		for( j = 1; j <= n-i; j++ )
		{
			if( data[j+1] < data[j] )
			{
				t         = data[j+1];
				data[j+1] = data[j];
				data[j]   = t;
			}
		}
		//输出每一轮排序结果 
		printf( "第 %d 趟排序：", i );
		for( k = 1; k <= n; k++  )
		{
			printf( "%5d", data[k] );
		}
		printf( "\n" );
	}
}

//从键盘读入一组整数存储到数组arr中，元素个数存储到count中 
void InputData( int &count, int arrt[] )
{
	int i = 0, data;
	while( 1 )
	{
		printf( "input an integer(end of 65535)" );
		scanf( "%d", &data );
		if( data == 65535 )
		{
			break;
		}
		else
		{
			arrt[++i] = data;
		}
	}
	count = i;
}

3.测试用例
测试用例一

测试用例二

四、算法改进

上述算法，从第二个测试用例可以发现，经过第一趟排序之后，数据就已经处于排好序的状态了，因此不需要再进行后续的排序。为了解决此问题，提高算法的效率，可以对上述算法进行改进。改进的方法之一是引入提前结束排序标志flag，进行每一趟排序前将其值置为1，表示可以提前结束，之后进行相邻的两个元素比较大小时，如果需要交换数据，则将flag的值置为0，表示不能提前结束。这样当进行某一趟排序时，如果不需要交换数据的操作，则表示数据已经处于排好序的状态了，此时就可以提前结束排序。

具体算法实现如下：

void BubbleSort_V1( int data[], int n )
{
	int i, j, k, t;
	bool flag;//提前结束排序的标志，1表示提前结束 
	for( i = 1; i <= n-1; i++ )
	{
		flag = 1;
		for( j = 1; j <= n-i; j++ )
		{
			if( data[j+1] < data[j] )
			{
				flag = 0; 
				t         = data[j+1];
				data[j+1] = data[j];
				data[j]   = t;
			}
		}
		//输出每一轮排序结果 
		printf( "第 %d 趟排序：", i );
		for( k = 1; k <= n; k++  )
		{
			printf( "%5d", data[k] );
		}
		printf( "\n" );
		
		if( flag == 1 )
		{
			break;
		}
	}
}

测试用例：

从测试用例可以发现，对于数组{11,15,8,19,2}，元素个数n=5,需要进行n-1=4趟排序得到最终的排序结果。对于数组{5,2,9,8,10}，元素个数n=5,只需要进行一趟排序就可以得到最终的排序结果。而改进的冒泡排序算法可以通过一趟排序即可以达成结果，因此其效率得到了提高。