冒泡排序

在冒泡排序的过程中，以升序排列为例，不断地比较数组中相邻的两个元素，较小者向上浮，较大者往下沉，整个过程和水中气泡上升的原理相似。接下来分步骤讲解冒泡排序的整个过程，具体如下。

第1步：从第1个元素开始，将相邻的两个元素依次进行比较，如果前一个元素比后一个元素大，则交换它们的位置，直到最后两个元素完成比较。整个过程完成后，数组中最后一个元素自然就是最大值，这样也就完成了第1轮的比较。

第2步：除了最后一个元素，将剩余的元素继续进行两两比较，过程与第1步相似，这样就可以将数组中第2大的元素放在倒数第2个位置。

第3步：以此类推，对剩余元素重复以上步骤。

根据上述步骤，冒泡排序的流程可使用图1描述。

图1 冒泡排序流程图（以升序排列为例）

定义一个数组：int arr[5]={9,8,3,5,2}，以数组arr为例，使用冒泡排序调整数组顺序的过程如图2所示。

图2 冒泡排序过程（以升序排列为例）

下面结合图2介绍数组arr排序过程。

第1轮比较中，第1个元素9为最大值，因此它在每次比较时都会发生位置的交换，最终被放到最后1个位置。

第2轮比较与第1轮过程相似，元素8被放到倒数第2个位置。

第3轮比较中，第1次比较没有发生位置的交换，在第2次比较时才发生位置交换，元素5被放到倒数第3个位置。

第4轮比较仅需比较最后两个值3和2，由于3比2大，3与2交换位置。

至此，数组中所有元素完成排序，获得排序结果{2,3,5,8,9}。

值得一提的是，当在程序中进行元素交换时，会通过一个中间变量temp实现元素交换，首先使用temp记录arr[j]，然后将arr[j+1]赋给arr[j]，最后再将temp赋给arr[j+1]。例如，交换数组元素8和3，其交换过程如图3所示。

图3 元素8与元素3交换过程

通过上面的分析可知，可以使用for循环遍历数组元素，因为每一轮数组元素都需要两两比较，所以需要嵌套for循环完成排序过程。其中，外层循环用来控制进行多少轮比较，每一轮比较都可以确定1个元素的位置；内层循环的循环变量用于控制每轮比较的次数，在每次比较时，如果前者小于后者，就交换两个元素的位置。需要注意的是，由于最后1个元素不需要进行比较，外层循环的次数为数组的长度-1。

接下来通过一个案例来演示冒泡排序，具体如例1所示。

例1 bubblingSort.c

 1  #include <stdio.h>
 2  int main()
 3  {
 4    int arr[5] = { 9,8,3,5,2 };
 5    int i, j, temp;
 6    printf("排序之前：");
 7    for (i = 0; i < 5; i++)
 8      printf("%d\t", arr[i]);
 9    for (i = 0; i < 5 - 1; i++)    //外层循环控制比较的轮数
 10   {
 11     for (j = 0; j < 5 - 1 - i; j++)  //内层循环控制比较的次数
 12     {  
 13       if (arr[j] > arr[j + 1])  //如果前面的元素大于后面的元素
 14       {             //就交换两个元素的位置
 15         temp = arr[j];
 16         arr[j] = arr[j + 1];
 17         arr[j + 1] = temp;
 18       }
 19     }
 20   }
 21   printf("\n排序之后：");
 22   for (i = 0; i < 5; i++)
 23     printf("%d\t", arr[i]);
 24   return 0;
 25 }

例1运行结果如图4所示。

图4 例1运行结果