冒泡排序的过程是把相邻的数据元素进行交换,从而逐步将待排序序列变成有序序列。冒泡排序的基本思想是:从头扫描待排序序列,在扫描的过程中顺次比较相邻两个元素的大小。
下面以升序为例介绍排序过程。
(1)在第一轮排序中,对n个记录进行如下操作。
①对相邻的两个记录的关键字进行比较,逆序时就交换位置。
②在扫描的过程中,不断向后移动相邻两个记录中关键字较大的记录。
③将待排序记录序列中的最大关键字记录交换到待排序记录序列的末尾,这也是最大关键字记录应在的位置。
(2)进行第二轮冒泡排序,对前n-1个记录进行同样的操作,其结果是使次大的记录被放在第n-2个记录的位置上。
(3)继续进行排序工作,在后面几轮的升序处理也反复遵循了上述过程,直到排好顺序为止。如果在某一轮冒泡过程中没有发现一个逆序,就可以马上结束冒泡排序。整个冒泡过程最多可以进行n-1轮,如图演示了一个完整的冒泡排序过程。
使用C语言实现冒泡排序的算法代码如下所示:
/*对数组 r 做冒泡排序,length为数组的长度*/
typedef int KeyType;
typedef struct {
KeyType key;
} RecordType ;
void BubbleSort(RecordType r[], int length ){
n=length;
change=TRUE;
for ( i=1 ; i<= n-1 && change ;++i ) {
change=FALSE;
for ( j=1 ; j<= n-i ; ++j)
if (r[j].key> r[j+1].key ) {
x= r[j];
r[j]= r[j+1];
r[j+1]= x;
change=TRUE;
}
}
} /* BubbleSort */