选择排序（Selection Sort）
选择排序每一轮只做一件事：从未排序区里挑出最小值，放到当前该放的位置。
定义
选择排序是一种简单直观的排序算法。它的工作原理是：每次从未排序部分选择**最小（或最大）**的元素，放到已排序部分的末尾。
核心思路
- 在未排序序列中找到最小（或最大）元素
- 将其与未排序部分的第一个元素交换
- 重复以上步骤，直到所有元素有序
初始: [64, 25, 12, 22, 11]
第1轮: 找到最小值11，与64交换 → [11, 25, 12, 22, 64]
第2轮: 找到最小值12，与25交换 → [11, 12, 25, 22, 64]
第3轮: 找到最小值22，与25交换 → [11, 12, 22, 25, 64]
第4轮: 找到最小值25，不交换 → [11, 12, 22, 25, 64]
完成: [11, 12, 22, 25, 64]
为什么它交换次数少
因为每一轮最多只做一次真正交换。
它会先把“本轮最小值在哪”找出来，最后再统一换过去，所以总交换次数最多是 n-1。
🎞️ 每轮选择最小值
（附件 selection-sort-min.svg 未随站点发布）
看动画时关注边界：左侧是已经排好序的区间，右侧每一轮只负责找出一个最小值。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间 | O(n²) | 无论数据状态，比较次数固定 |
| 平均时间 | O(n²) | (n-1) + (n-2) + … + 1 = n(n-1)/2 |
| 最坏时间 | O(n²) | 同上 |
| 空间复杂度 | O(1) | 原地排序 |
| 稳定性 | ❌ 不稳定 | 交换可能改变相等元素的相对位置 |
Go 代码
Go 实现
package main
import "fmt"
func selectionSort(arr []int) {
n := len(arr)
for i := 0; i < n-1; i++ {
minIdx := i
// 找到未排序部分的最小值索引
for j := i + 1; j < n; j++ {
if arr[j] < arr[minIdx] {
minIdx = j
}
}
// 交换
if minIdx != i {
arr[i], arr[minIdx] = arr[minIdx], arr[i]
}
}
}
func main() {
arr := []int{64, 25, 12, 22, 11}
fmt.Println("原始数组:", arr)
selectionSort(arr)
fmt.Println("排序后:", arr)
}易错点
选择排序最容易写对，但也最容易忽略它为什么不稳定。
- 每轮确定的是“最小值位置”，不是遇到更小就立刻交换。
- 稳定性被破坏，是因为最小值可能跨过若干个相等元素直接换到前面。
- 即使数组几乎有序，选择排序的比较次数也不会明显下降。
算法变体
- 选择最大值：每轮把未排序区间的最大值放到右侧，适合从后往前固定位置。
- 双向选择排序：一轮同时找最小值和最大值，分别放到左端和右端，仍然是
O(n²)比较。 - 部分选择：只执行前
k轮即可得到前k个最小元素，但未排序区间本身不保证有序。 - 快速选择：如果只关心第
k小，不必每轮扫描全部剩余元素，可以改用 partition 把平均复杂度降到O(n)。
经典题目
基础应用
- 排序数组 - LeetCode 912
- 数组中的第K个最大元素 - LeetCode 215（选择K次）
变体题目
- 选择排序的交换次数最少
- 使用选择排序找第k小元素
- 优化选择排序的比较次数
优缺点
优点
- ✅ 实现简单
- ✅ 原地排序（O(1)空间）
- ✅ 交换次数少：最多n-1次交换
- ✅ 性能稳定：无论数据状态，比较次数固定
缺点
- ❌ 时间复杂度高 O(n²)
- ❌ 不稳定：交换操作可能改变相等元素顺序
- ❌ 比较次数固定，无法利用数据的有序性
- ❌ 不适合链表（需要随机访问）
应用场景
- 交换代价高：当交换元素的代价远大于比较时
- 小数据集：数据量很小
- 内存受限：需要原地排序
- 不需要稳定性：对稳定性无要求
选择排序 vs 冒泡排序
| 特性 | 选择排序 | 冒泡排序 |
|---|---|---|
| 时间复杂度 | O(n²) | O(n²) |
| 交换次数 | O(n) | O(n²) |
| 稳定性 | 不稳定 | 稳定 |
| 适用场景 | 交换代价高 | 需要稳定性 |