冒泡排序(Bubble Sort)算法又称为泡沫排序算法,是基本的排序算法,是学习编程语言最先需要学会的排序算法之一。顾名思义,就是它的排序方式如同气泡一般,不断将最大的元素挤出(移动)到串行最尾端,当所有元素都被挤出后,排序就完成了!而且排序结果是稳定的。

冒泡排序法(Bubble Sort)

冒泡排序法的概念

冒泡排序法会从串行最前方开始进行走访,在每次迭代时,会拿当前索引位置的元素与其下一个索引位置的元素进行比较,如果下一个元素比较小,就进行交换;如果下一个元素没有比较小,就不进行交换。当串行被走访完一次之后,串行的最尾端元素即为最大的元素。再来重新走访一次串行,用同样的方法将第二大的元素值挤进串行的从尾端开始倒数的第二个位置。然后重新走访一次串行,用同样的方法将第三大的元素值挤进串行的从尾端开始倒数的第三个位置。依此类推,直到所有元素都被挤到尾端,或是在走访串行的过程中,如果发现都没有元素被交换的话,表示此时的串行已经完成排序了。

冒泡排序法的过程

假设现在有个数组数据,内容如下:

索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

要如何将它递增排列呢?

一开始,要将重点聚焦于数组最尾端的位置,因为我们要先将整个数组的最大值移动到数组的最尾端。

从数组最前方开始,逐次两两比较元素的大小,将两个元素中较大的元素排在后面,即可逐渐将最大的元素从数组前方挤到数组后方。这就像是沉在水中的大气泡,想要漂浮到水面上前,必须挤开其它的小气泡一样。

所以,若要挤出数组的最大值至数组的最尾端,位于数组最前端的 69,要跟它之后的元素 81 比大小,如下表:

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79
       └┬┘
      69 < 81

由于 69 比 81 小,所以不用换位置。然后再比 81 和 30 的大小,如下表:

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79
           └┬┘
          81 > 30

81 比 30 大,所以 81 会挤开 30,与 30 交换,排在 30 之后。

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  81  38   9   2  47  61  32  79
           └─┘

然后再比较 81 和 38 的大小,如下表:

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  81  38   9   2  47  61  32  79
               └┬┘
              81 > 38

81 比 38 大,所以 81 会挤开 38,与 38 交换,排在 38 之后。

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38  81   9   2  47  61  32  79
               └─┘

继续判断大小并移动,直到最大值被挤到数组最尾端:

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38  81   9   2  47  61  32  79
                   └┬┘
                  81 > 9

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9  81   2  47  61  32  79
                   └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9  81   2  47  61  32  79
                       └┬┘
                      81 > 2

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  81  47  61  32  79
                       └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  81  47  61  32  79
                           └┬┘
                          81 > 47

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  81  61  32  79
                           └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  81  61  32  79
                               └┬┘
                              81 > 61

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  81  32  79
                               └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  81  32  79
                                   └┬┘
                                  81 > 32

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  81  79
                                   └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  81  79
                                       └┬┘
                                      81 > 79

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81
                                       └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81

如此一来,数组中的最大元素 81 就成功被挤出至最尾端了。接着用同样的方法继续找出第二大的元素,并将其挤出至从尾端开始倒数的第二个位置,再找出第三大的元素,并将其挤出至从尾端开始倒数的第三个位置。直到所有元素都被挤出为止,数组就排序完成了!完整过程如下:

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79
       └┬┘
      69 < 81

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79
           └┬┘
          81 > 30

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  81  38   9   2  47  61  32  79
           └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  81  38   9   2  47  61  32  79
               └┬┘
              81 > 38

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38  81   9   2  47  61  32  79
               └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38  81   9   2  47  61  32  79
                   └┬┘
                  81 > 9

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9  81   2  47  61  32  79
                   └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9  81   2  47  61  32  79
                       └┬┘
                      81 > 2

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  81  47  61  32  79
                       └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  81  47  61  32  79
                           └┬┘
                          81 > 47

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  81  61  32  79
                           └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  81  61  32  79
                               └┬┘
                              81 > 61

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  81  32  79
                               └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  81  32  79
                                   └┬┘
                                  81 > 32

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  81  79
                                   └─┘

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  81  79
                                       └┬┘
                                      81 > 79

                                           ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81
                                       └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   69  30  38   9   2  47  61  32  79  81
       └┬┘
      69 > 30

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  69  38   9   2  47  61  32  79  81
       └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  69  38   9   2  47  61  32  79  81
           └┬┘
          69 > 38

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38  69   9   2  47  61  32  79  81
           └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38  69   9   2  47  61  32  79  81
               └┬┘
              69 > 9

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9  69   2  47  61  32  79  81
               └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9  69   2  47  61  32  79  81
                   └┬┘
                  69 > 2

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9   2  69  47  61  32  79  81
                   └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9   2  69  47  61  32  79  81
                       └┬┘
                      69 > 47

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9   2  47  69  61  32  79  81
                       └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9   2  47  69  61  32  79  81
                           └┬┘
                          69 > 61

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9   2  47  61  69  32  79  81
                           └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9   2  47  61  69  32  79  81
                               └┬┘
                              69 > 32

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9   2  47  61  32  69  79  81
                               └─┘

                                       ●  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9   2  47  61  32  69  79  81
                                   └┬┘
                                  69 < 79

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9   2  47  61  32  69  79  81

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9   2  47  61  32  69  79  81
       └┬┘
      30 < 38

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30  38   9   2  47  61  32  69  79  81
           └┬┘
          38 > 9

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30   9  38   2  47  61  32  69  79  81
           └─┘

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30   9  38   2  47  61  32  69  79  81
               └┬┘
              38 > 2

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30   9   2  38  47  61  32  69  79  81
               └─┘

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30   9   2  38  47  61  32  69  79  81
                   └┬┘
                  38 < 47

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30   9   2  38  47  61  32  69  79  81
                       └┬┘
                      47 < 61

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30   9   2  38  47  61  32  69  79  81
                           └┬┘
                          61 > 32

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30   9   2  38  47  32  61  69  79  81
                           └─┘

                                   ●  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30   9   2  38  47  32  61  69  79  81
                               └┬┘
                              61 < 69

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30   9   2  38  47  32  61  69  79  81

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值   30   9   2  38  47  32  61  69  79  81
       └┬┘
      30 > 9

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    9  30   2  38  47  32  61  69  79  81
       └─┘

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    9  30   2  38  47  32  61  69  79  81
           └┬┘
          30 > 2

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    9   2  30  38  47  32  61  69  79  81
           └─┘

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    9   2  30  38  47  32  61  69  79  81
               └┬┘
              30 < 38

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    9   2  30  38  47  32  61  69  79  81
                   └┬┘
                  38 < 47

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    9   2  30  38  47  32  61  69  79  81
                       └┬┘
                      47 > 32

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    9   2  30  38  32  47  61  69  79  81
                       └─┘

                               ●  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    9   2  30  38  32  47  61  69  79  81
                           └┬┘
                          47 < 61

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    9   2  30  38  32  47  61  69  79  81

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    9   2  30  38  32  47  61  69  79  81
       └┬┘
       9 > 2

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  38  32  47  61  69  79  81
       └─┘

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  38  32  47  61  69  79  81
           └┬┘
           9 < 30

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  38  32  47  61  69  79  81
               └┬┘
               30 < 38

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  38  32  47  61  69  79  81
                   └┬┘
                   38 > 32

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                   └─┘

                           ●  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                       └┬┘
                       38 < 47

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
       └┬┘
       2 < 9

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
           └┬┘
           9 < 30

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
               └┬┘
               30 < 32

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                   └┬┘
                   32 < 38

                       ●  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8   9
数值    2   9  30  32  38  47  61  69  79  81
                       ※

冒泡排序法的排序过程动画

冒泡排序法的程序实作

冒泡排序法的复杂度

以 #{{n}}# 来表示要排序的数据笔数。

项目 值 备注
最差时间复杂度 #{{O(n^2)}}# 排序已经反向排序过的串行。
最佳时间复杂度 #{{O(n)}}# 排序已经正向排序过的串行。
平均时间复杂度 #{{O(n^2)}}#
最差空间复杂度 #{{O(1)}}#
是否稳定 是