选择排序(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
               └─┬─┘
                30 > 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

选择排序法的排序过程动画

选择排序法的程序实作

选择排序法的复杂度

以 #{{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  81  69  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  69  81  38  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  38  81  69  30   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  30  81  69  38   9  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  81  69  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  69  81  38  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  38  81  69  30  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  81  69  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  69  81  38  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 < 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  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
                       └┬┘
                      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  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  69  81  47  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  47  81  69  61  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
                       └────┬────┘
                              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  81  69  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  69  81  61  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  61  81  69  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
                           └───┬───┘
                                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  81  69  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  69  81  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
                               └──┬──┘
                                  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  81  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
                                   └─┬─┘
                                    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  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

交换排序法的排序过程动画

交换排序法的程序实作

交换排序法的复杂度

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

项目 值 备注
最差时间复杂度 #{{O(n^2)}}#
最佳时间复杂度 #{{O(n^2)}}#
平均时间复杂度 #{{O(n^2)}}#
最差空间复杂度 #{{O(1)}}#
是否稳定 否