11.2　冒泡法排序

本节介绍冒泡法排序的实现方法。首先确定所要采用的排序规则是升序还是降序。所谓升序，就是将给定的一组数据按照由小到大的顺序排列，而降序则与之相反。冒泡法排序就是依次比较相邻的两个数，根据采用的排序规则决定是否交换两个数的位置。

在此以升序为例来进行讲解。

第一轮：先比较第一个数和第二个数，将小数放前，大数放后，然后比较第二个数和第三个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。到第一轮结束的时候，已经成功地将最大的数放到了最后。

第二轮：可能由于第二个数和第三个数的交换，使第一个数不再小于第二个数，所以新一轮的比较仍从第一对数开始比较，将小数放前，大数放后，一直比较到倒数第二个数，由于最后一个位置上的数已经是最大的，所以无须再对其进行比较。到第二轮结束的时候，在倒数第二个位置上得到一个新的最大数，也就是给定数据中的第二大的数。

重复以上过程，直到最后一轮比较完第一个数和第二个数，完成整个排序功能。接下来看下面的代码。

include＜stdio.h＞

void bubble_sort（int arr[]，int n）

{

int i,j，temp；

for（i=0；i＜n-1；i++）

for（j=0；j＜n-i-1；j++）

{

if（arr[j]＞arr[j+1]）

{

temp=arr[j]；

arr[j]=arr[j+1]；

arr[j+1]=temp；

}

}

return；

}

int main（）

{

int a[]={91，54，32，87，46}；

int i；

printf（"排序前\n"）；

for（i=0；i＜5；i++）

printf（"%d\t"，a[i]）；

bubble_sort（a，5）；

printf（"\n排序后\n"）；

for（i=0；i＜5；i++）

printf（"%d\t"，a[i]）；

return 0；

}

运行结果：

排序前

91 54 32 87 46

排序后

32 46 54 87 91

上面的代码，成功地实现了对给定数组的排序，接下来通过图来分析每轮的排序工作，图11-1演示的是第一轮的比较操作。

图　11-1　第一轮的比较操作

图11-1中第一轮比较后的结果是进行下一轮排序的基础，接下来通过图11-2来了解第二轮的比较操作。

图　11-2　第二轮的比较操作

下面在第二轮比较结果的基础上进行下一轮比较。图11-3为第三轮的比较操作。

分析上面的比较结果可以发现，第三轮结束之后的比较结果就是最终的结果了，没有必要再进行接下来的比较操作了，但是计算机并不知道，它还会进行接下来的比较操作。为了改进冒泡法排序的这一缺点，防止对已经完成排序功能的数据进行没有任何意义的比较操作，我们定义一个标识符flag，在每轮比较操作之前将flag赋值为1，如果在该轮比较操作中发现排序没有完成，那么就在该轮结束时将其赋值为0，否则不改变其flag值，在下一轮开始前对flag进行判断，如果其值为1，表示在上一轮排序中发现已经完成了排序功能，那么就结束冒泡法排序的比较操作。接下来看改进后的代码。

图　11-3　第三轮的比较操作

include＜stdio.h＞

void bubble_sort（int arr[]，int n）

{

int i,j，flag,temp；

for（i=0；i＜n-1；i++）

{

flag=1；

for（j=0；j＜n-i-1；j++）

{

if（arr[j]＞arr[j+1]）

{

temp=arr[j]；

arr[j]=arr[j+1]；

arr[j+1]=temp；

flag=0；

}

}

if（1==flag）

break；

}

printf（"\n比较操作进行了%d轮"，i+1）；

return；

}

int main（）

{

int a[]={12，54，67，89，96}；

int i；

printf（"排序前\n"）；

for（i=0；i＜5；i++）

printf（"%d\t"，a[i]）；

bubble_sort（a，5）；

printf（"\n排序后\n"）；

for（i=0；i＜5；i++）

printf（"%d\t"，a[i]）；

return 0；

}

运行结果：

排序前

12 54 67 89 96

比较操作进行了1轮

排序后

12 54 67 89 96

在上面的代码中，在排序中加了一个打印输出语句，用于输出比较操作进行了多少轮。由于最初给定的数组是一个有序的数组，因此比较操作只进行了一轮，但是如果没有在代码中使用标识符flag，那么即使是对有序的数组进行排序，同样要进行5轮排序操作。使用标识符之后，算法的效率得到了提高。

根据前面讲解的时间复杂度可以得出，冒泡法排序的时间复杂度是O（n²）。