冒泡排序算法详解之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 100int 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,只需要进行一趟排序就可以得到最终的排序结果。而改进的冒泡排序算法可以通过一趟排序即可以达成结果，因此其效率得到了提高。