选择排序

一、算法描述

1.1 核心思想

• 数据分为已排序区间和未排序区间
• 从未排序区间中找到最小/最大的元素，放到到已排序区间的尾部
• 执行 n 轮后，所有未排序元素都会迁移到已排序区间中

1.2 细节解释

比如说，数组 [2, 7, 1, 4, 3, 6, 5]。

首先分成未排序和已排序区间，已排序区间一开始是空的：

已排序                           未排序
                                  ___ ___ ___ ___ ___ ___ ___
                                 | 2 | 7 | 1 | 4 | 3 | 6 | 5 |

首先找到未排序区间的最小值，也就是 1，将 1 迁移到已排序区间中：

 已排序                           未排序
 ___                               ___ ___ ___ ___ ___ ___
| 1 |                             | 7 | 2 | 4 | 3 | 6 | 5 |

继续从未排序区间找最小值，得到 2，然后将 2 移动到已排序区间：

 已排序                           未排序
 ___ ___                           ___ ___ ___ ___ ___
| 1 | 2 |                         | 7 | 4 | 3 | 6 | 5 |

以此类推，分别交换得到 3、4、5、6、7 的最终位置：

 已排序                           未排序
 ___ ___ ___                       ___ ___ ___ ___
| 1 | 2 | 3 |                     | 4 | 7 | 6 | 5 |

 已排序                           未排序
 ___ ___ ___ ___                   ___ ___ ___
| 1 | 2 | 3 | 4 |                 | 7 | 6 | 5 |

 已排序                           未排序
 ___ ___ ___ ___ ___               ___ ___
| 1 | 2 | 3 | 4 | 5 |             | 6 | 7 |

 已排序                           未排序
 ___ ___ ___ ___ ___ ___           ___
| 1 | 2 | 3 | 4 | 5 | 6 |         | 7 |

 已排序                           未排序
 ___ ___ ___ ___ ___ ___ ___ 
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |

经过 n 轮交换，数组就排好序了。

二、算法实现

public void selectSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        // 寻找未排序区间内的最小值
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        // 将最小值插入到已排序区间的末尾
        swap(arr, min, i);
    }
}

执行过程如下：

=====  初始数组 =====
[0, 3, 1, 6, 2, 5, 4]

=====第 1 轮插入=====
[0, 3, 1, 6, 2, 5, 4]

=====第 2 轮插入=====
[0, 1, 3, 6, 2, 5, 4]

=====第 3 轮插入=====
[0, 1, 2, 6, 3, 5, 4]

=====第 4 轮插入=====
[0, 1, 2, 3, 6, 5, 4]

=====第 5 轮插入=====
[0, 1, 2, 3, 4, 5, 6]

=====第 6 轮插入=====
[0, 1, 2, 3, 4, 5, 6]

=====第 7 轮插入=====
[0, 1, 2, 3, 4, 5, 6]

三、算法分析

3.1 时间复杂度

• 最好时间复杂度：O(n^2)
• 最坏时间复杂度：O(n^2)
• 平均时间复杂度：O(n^2)

3.2 空间复杂度

• 空间复杂度：O(1)
• 原地算法

3.3 稳定性

• 不稳定排序算法

附录

/**
 * 选择排序
 * <p>
 * 时间复杂度：最好 O(n^2) 最差 O(n^2) 平均 O(n^2)
 * <p>
 * 空间复杂度：O(1)
 * <p>
 * 稳定性：不稳定
 *
 * @author weijiaduo
 * @since 2022/7/21
 */
public class SelectSort implements Sort {

    @Override
    public void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // 寻找未排序区间内的最小值
            int min = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // 将最小值插入到已排序区间的末尾
            swap(arr, min, i);
        }
    }

}