選擇排序(Selection Sort)演算法，最簡單的排序演算法

選擇排序(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

因為69比81小，所以再比較下一個索引值的元素的大小，如下表：

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

69比30大，所以目前最小元素的索引位置變成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

選擇排序法的程式實作

/// 選擇排序法(遞增)。
pub fn selection_sort(array: &mut [i32]) {
    for i in 0..(array.len() - 1) {
        let mut p = i;

        for (j, e) in array[(i + 1)..].iter().copied().enumerate() {
            if array[p] > e {
                p = j + i + 1;
            }
        }

        if i != p {
            array.swap(i, p);
        }
    }
}

/// 選擇排序法(遞減)。
pub fn selection_sort_desc(array: &mut [i32]) {
    for i in 0..(array.len() - 1) {
        let mut p = i;

        for (j, e) in array[(i + 1)..].iter().copied().enumerate() {
            if array[p] < e {
                p = j + i + 1;
            }
        }

        if i != p {
            array.swap(i, p);
        }
    }
}

/**
 * 選擇排序法(遞增)。
 */
public static void selectionSort(final int[] array) {
    final int length = array.length;
    final int lengthDec = length - 1;

    for (int i = 0; i < lengthDec; ++i) {
        int p = i;

        for (int j = i + 1; j < length; ++j) {
            if (array[p] > array[j]) {
                p = j;
            }
        }

        if (i != p) {
            int temp = array[i];
            array[i] = array[p];
            array[p] = temp;
        }
    }
}

/**
 * 選擇排序法(遞減)。
 */
public static void selectionSortDesc(final int[] array) {
    final int length = array.length;
    final int lengthDec = length - 1;

    for (int i = 0; i < lengthDec; ++i) {
        int p = i;

        for (int j = i + 1; j < length; ++j) {
            if (array[p] < array[j]) {
                p = j;
            }
        }

        if (i != p) {
            int temp = array[i];
            array[i] = array[p];
            array[p] = temp;
        }
    }
}

/**
 * 選擇排序法(遞增)。
 */
function selectionSort(array: number[]) {
    const length = array.length;
    const lengthDec = length - 1;

    for (let i = 0;i < lengthDec;++i) {
        let p = i;

        for (let j = i + 1;j < length;++j) {
            if (array[p] > array[j]) {
                p = j;
            }
        }

        if (i !== p) {
            const temp = array[i];
            array[i] = array[p];
            array[p] = temp;
        }
    }
}

/**
 * 選擇排序法(遞減)。
 */
function selectionSortDesc(array: number[]) {
    const length = array.length;
    const lengthDec = length - 1;

    for (let i = 0;i < lengthDec;++i) {
        let p = i;

        for (let j = i + 1;j < length;++j) {
            if (array[p] < array[j]) {
                p = j;
            }
        }

        if (i !== p) {
            const temp = array[i];
            array[i] = array[p];
            array[p] = temp;
        }
    }
}

// 選擇排序法(遞增)。
func SelectionSort(array []int) {
	length := len(array)
	lengthDec := length - 1

	for i := 0; i < lengthDec; i += 1 {
		p := i

		for j := i + 1; j < length; j += 1 {
			if array[p] > array[j] {
				p = j
			}
		}

		array[i], array[p] = array[p], array[i]
	}
}

// 選擇排序法(遞減)。
func SelectionSortDesc(array []int) {
	length := len(array)
	lengthDec := length - 1

	for i := 0; i < lengthDec; i += 1 {
		p := i

		for j := i + 1; j < length; j += 1 {
			if array[p] < array[j] {
				p = j
			}
		}

		array[i], array[p] = array[p], array[i]
	}
}

選擇排序法的複雜度

交換排序法(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

交換排序法的程式實作

/// 交換排序法(遞增)。
pub fn exchange_sort(array: &mut [i32]) {
    let length = array.len();

    for i in 0..(length - 1) {
        for j in (i + 1)..length {
            if array[i] > array[j] {
                array.swap(i, j);
            }
        }
    }
}

/// 交換排序法(遞減)。
pub fn exchange_sort_desc(array: &mut [i32]) {
    let length = array.len();

    for i in 0..(length - 1) {
        for j in (i + 1)..length {
            if array[i] < array[j] {
                array.swap(i, j);
            }
        }
    }
}

/**
 * 交換排序法(遞增)。
 */
public static void exchangeSort(final int[] array) {
    final int length = array.length;
    final int lengthDec = length - 1;

    for (int i = 0; i < lengthDec; ++i) {
        for (int j = i + 1; j < length; ++j) {
            if (array[i] > array[j]) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
}

/**
 * 交換排序法(遞減)。
 */
public static void exchangeSortDesc(final int[] array) {
    final int length = array.length;
    final int lengthDec = length - 1;

    for (int i = 0; i < lengthDec; ++i) {
        for (int j = i + 1; j < length; ++j) {
            if (array[i] < array[j]) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
}

/**
 * 交換排序法(遞增)。
 */
function exchangeSort(array: number[]) {
    const length = array.length;
    const lengthDec = length - 1;

    for (let i = 0;i < lengthDec;++i) {
        for (let j = i + 1;j < length;++j) {
            if (array[i] > array[j]) {
                const temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
}

/**
 * 交換排序法(遞減)。
 */
function exchangeSortDesc(array: number[]) {
    const length = array.length;
    const lengthDec = length - 1;

    for (let i = 0;i < lengthDec;++i) {
        for (let j = i + 1;j < length;++j) {
            if (array[i] < array[j]) {
                const temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
}

// 交換排序法(遞增)。
func ExchangeSort(array []int) {
	length := len(array)
	lengthDec := length - 1

	for i := 0; i < lengthDec; i += 1 {
		for j := i + 1; j < length; j += 1 {
			if array[i] > array[j] {
				array[i], array[j] = array[j], array[i]
			}
		}
	}
}

// 交換排序法(遞減)。
func ExchangeSortDesc(array []int) {
	length := len(array)
	lengthDec := length - 1

	for i := 0; i < lengthDec; i += 1 {
		for j := i + 1; j < length; j += 1 {
			if array[i] < array[j] {
				array[i], array[j] = array[j], array[i]
			}
		}
	}
}

交換排序法的複雜度