学科分类
目录
C语言

冒泡排序

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

第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运行结果

点击此处
隐藏目录