選擇排序(Selection Sort)演算法是最基本的排序演算法,是學習程式語言最先需要學會的排序演算法之一。它可以按照元素值的大小序次,一一將最小值、第二小值等等的元素排入序列中的正確索引位置內。



選擇排序法(Selection Sort)

選擇排序法的概念

選擇排序法是以土法煉鋼的方式按照次序走訪序列中的每個索引位置,並在每次迭代時去往後選擇出剩餘的最小元素值,來與目前的索引位置的元素做交換。如此一來,序列中的元素就能以遞增的方式來排列。

至於要如何「往後選擇出剩餘的最大元素值或最小元素值」呢?我們可以先假設目前索引位置的元素值是最小的,然後再去走訪之後的所有元素,如果發現有比目前索引位置的元素值還小的元素,就把它的索引值記下來,然後再繼續走訪,再用其它走訪到的元素與目前記下的索引位置的元素值進行比較,如果又發現更小的,就再把索引值記下。如此一來,剩餘的元素走訪完之後,就知道其中最小值的索引位置了。如果這個索引位置並不是目前走訪到的索引位置,就把這兩個索引位置的元素做交換。

所以說,在走訪到序列的第一個元素,並按照上述方式處理完成之後,序列的第一個元素必定會是最小值。在走訪到序列的第二個元素,並按照上述方式處理完成之後,序列的第二個元素必定會是第二小值。

選擇排序法的過程

假設現在有個陣列資料,內容如下:

索引    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
       →

再與其之後的元素比大小,若找到比目前假設最小元素還小的元素,就記下索引值,如下表:

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

因為6981小,所以再比較下一個索引值的元素的大小,如下表:

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

6930大,所以目前最小元素的索引位置變成2

       ●
               ※
索引    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
               └┬┘
              30 < 38

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

       ●
                       ※
索引    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
                       └┬┘
                       9 > 2

       ●
                           ※
索引    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
                           └┬┘
                           2 < 47

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

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

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

       ●
                           ※
索引    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
數值    2  81  30  38   9  69  47  61  32  79
       └─────────┘

接著用同樣的方法繼續找出第二小的元素,並將其交換至前端第二個位置,再找出第三小的元素,並將其交換至前端第三個位置。直到所有元素位置都被確認過之後,陣列就排序完成了!完整過程如下:

       ●
       ※
索引    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
       └─┬─┘
        69 > 30

       ●
               ※
索引    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
               └┬┘
              30 < 38

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

       ●
                       ※
索引    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
                       └┬┘
                       9 > 2

       ●
                           ※
索引    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
                           └┬┘
                           2 < 47

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

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

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

       ●
                           ※
索引    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
數值    2  81  30  38   9  69  47  61  32  79
       └─────────┘

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

       ○  ○  ○  ○  ○  ○  ○  ○  ●
                                           ※      
索引    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

selection-sort

選擇排序法的程式實作

選擇排序法的複雜度

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

項目備註
最差時間複雜度#{{O(n^2)}}#
最佳時間複雜度#{{O(n^2)}}#
平均時間複雜度#{{O(n^2)}}#
額外最差空間複雜度#{{O(1)}}#
是否穩定

交換排序法(Exchange Sort)

交換排序法的概念

交換排序法與上面介紹的選擇排序法非常類似,只不過交換排序法不使用而外的空間來儲存走訪序列時找到的當前最小元素的索引值,而是直接將找到的較小元素進行交換。由於這個演算法需要在序列中一直做交換元素的動作,因此在絕大部分情況下會比選擇排序法還慢,幾乎沒有人會想使用這個演算法,這也是為什麼筆者會將它放到這篇文章的最後來做介紹。

交換排序法的過程

假設現在有個陣列資料,內容如下:

索引    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
       →

再與其之後的元素比大小,若找到比目前走訪到的元素還小的元素,就直接進行交換,然後繼續往下找;若沒找到比目前走訪到的元素還小的元素,就不進行交換,然後繼續往下找。完整過程如下:

       ●
索引    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
       └─┬─┘
        69 > 30

       ●
索引    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
數值   30  81  69  38   9   2  47  61  32  79
       └───┘

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

       ○  ○  ○  ○  ○  ○  ○  ○  ●
索引    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
                                       └─┘

       ○  ○  ○  ○  ○  ○  ○  ○  ○

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

selection-sort

交換排序法的程式實作

交換排序法的複雜度

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

項目備註
最差時間複雜度#{{O(n^2)}}#
最佳時間複雜度#{{O(n^2)}}#
平均時間複雜度#{{O(n^2)}}#
額外最差空間複雜度#{{O(1)}}#
是否穩定