选择排序

定义¶

选择排序（英语：Selection sort）是一种简单直观的排序算法。

它的工作原理是每次找出第 $i$ 小的元素（也就是 $A_{i..n}$ 中最小的元素），然后将这个元素与数组第 $i$ 个位置上的元素交换。

具体说明与示例¶

下面通过一个示例来直观理解选择排序的原理。假设待排序数组为：

A = [64, 25, 12, 22, 11]

第一轮（$i = 1$）
- 在 A[1..5] 中寻找最小值，元素依次为 64、25、12、22、11，最小值是 $11$，位置 pos = 5。
- 将 A[1] 与 A[5] 交换，结果：
```
[11, 25, 12, 22, 64]
```
第二轮（$i = 2$）
- 在 A[2..5] 中寻找最小值，元素依次为 25、12、22、64，最小值是 $12$，位置 pos = 3。
- 将 A[2] 与 A[3] 交换，结果：
```
[11, 12, 25, 22, 64]
```
第三轮（$i = 3$）
- 在 A[3..5] 中寻找最小值，元素依次为 25、22、64，最小值是 $22$，位置 pos = 4。
- 将 A[3] 与 A[4] 交换，结果：
```
[11, 12, 22, 25, 64]
```
第四轮（$i = 4$）
- 在 A[4..5] 中寻找最小值，元素依次为 25、64，最小值是 $25$，位置 pos = 4。
- 将 A[4] 与 A[4] 交换，数组保持不变：
```
[11, 12, 22, 25, 64]
```
完成排序
- 前四轮后，数组已按升序排列，最后一个元素自然有序。

具体实现¶

设待排序数组为 A[1..n]：

外层循环：依次遍历位置 i，i 从 1 到 n-1。
寻找最小值：在子数组 A[i..n] 中找到最小元素的位置，记为 pos。
- 初始化 pos = i。
- 对于每个 j 从 i+1 到 n，若 A[j] < A[pos]，则更新 pos = j。
- 交换元素：将 A[i] 与 A[pos] 交换，使得 A[i] 存放当前子数组的最小值。
- 重复以上步骤，直到第 n-1 个位置完成，最后一个元素自然有序。

伪代码

\[\begin{array}{ll} 1 & \textbf{for } i\gets 1\textbf{ to }n-1\\ 2 & \qquad pos\gets i\\ 3 & \qquad \textbf{for }j\gets i+1\textbf{ to }n\\ 4 & \qquad\qquad\textbf{if }A[j]<A[pos]\\ 5 & \qquad\qquad\qquad pos\gets j\\ 6 & \qquad \text{swap }A[i]\text{ and }A[pos]\\ \end{array}\]

性质¶

稳定性¶

选择排序是不稳定的。

例如序列 $a=[\textcolor{red}{2}, \textcolor{blue}{2}, \textcolor{blue}{1}]$

根据选择排序的思想，我们会先找到序列中最小值的位置 $3$，然后交换 $a[1]$ 与 $a[3]$ 后得到 $a=[\textcolor{blue}{1}, \textcolor{blue}{2}, \textcolor{red}{2}]$。

可以发现红色的 $2$ 跑到了蓝色的 $2$ 后面，相当的元素相对顺序发生了改变，因此是不稳定的。

复杂度¶

选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 $O(n^2)$。