氣泡排序(Selection 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

由於6981小,所以不用換位置。然後再比8130的大小,如下表:

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

8130大,所以81會擠開30,與30交換,排在30之後。

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

然後再比較8138的大小,如下表:

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

8138大,所以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  69  61  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
                       ※

bubble-sort

氣泡排序法的程式實作

氣泡排序法的複雜度

以#{{n}}#來表示要排序的資料筆數。

項目 備註
最差時間複雜度 #{{O(n^2)}}# 排序已經反向排序過的序列。
最佳時間複雜度 #{{O(n)}}# 排序已經正向排序過的序列。
平均時間複雜度 #{{O(n^2)}}#
最差空間複雜度 #{{O(1)}}#
是否穩定