选择排序（Selection Sort）
每次从未排序部分选择最小值，放到已排序部分的末尾。简单朴素但存在三个主要缺陷：不稳定、无法利用有序性、无法优化。
定义
选择排序（Selection Sort）是最简单朴素的排序算法之一。其核心思想是：
每次从右侧未排序部分选择最小值，放到左侧已排序部分的末尾。
核心特性
| 特性 | 说明 |
|---|---|
| 时间复杂度 | O(n²)，无论输入如何都是 O(n²) |
| 空间复杂度 | O(1)，原地排序 |
| 稳定性 | ❌ 不稳定（交换可能改变相同元素相对位置） |
| 是否原地 | ✅ 是 |
| 突破性 | ❌ 无法突破 O(n²) |
基本原理
算法过程
- 初始状态：
[0, sortedIndex)为已排序部分，sortedIndex初始为 0 - 每次迭代：在
[sortedIndex, n)未排序部分找到最小值 - 将最小值与
nums[sortedIndex]交换 sortedIndex++，扩大已排序部分
void sort(int[] nums) {
int n = nums.length;
int sortedIndex = 0;
while (sortedIndex < n) {
// 在 [sortedIndex, n) 中找到最小值的索引
int minIndex = sortedIndex;
for (int i = sortedIndex + 1; i < n; i++) {
if (nums[i] < nums[minIndex]) {
minIndex = i;
}
}
// 将最小值交换到 sortedIndex 位置
int tmp = nums[sortedIndex];
nums[sortedIndex] = nums[minIndex];
nums[minIndex] = tmp;
sortedIndex++;
}
}
三个主要缺陷
- 不稳定：交换操作可能改变相同元素的相对位置
- 无法利用有序性：无论数组是否有序，都要完整执行 O(n²) 次操作
- 无法优化：尝试用 suffixMin 预处理来优化，但遇到交换导致的不稳定性问题
与类似概念对比
| 维度 | 选择排序 | 插入排序 | 冒泡排序 |
|---|---|---|---|
| 时间复杂度 | O(n²) | O(n²) | O(n²) |
| 空间复杂度 | O(1) | O(1) | O(1) |
| 稳定性 | ❌ 不稳定 | ✅ 稳定 | ✅ 稳定 |
| 提前终止 | ❌ 不支持 | ✅ 支持（利用有序性） | ✅ 支持 |
| 有序度利用 | ❌ 不利用 | ✅ 高效 | ⚠️ 利用但效率低 |
| 优化潜力 | ❌ 无 | ✅ 有（希尔排序等） | ⚠️ 有限 |
时间复杂度/性能
| 场景 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n²) | 即使已排序也要完整执行 |
| 最坏情况 | O(n²) | 完全逆序 |
| 平均情况 | O(n²) | 操作次数固定 = n(n-1)/2 |
| 与输入关系 | 无关 | 无论输入如何都是 O(n²) |
注意事项
- 交换导致不稳定：
swap(minIndex, sortedIndex)可能改变相同元素的相对位置 - 无法利用有序性：即使数组已经有序，仍然执行完整的 O(n²) 次比较
- 优化尝试失败：尝试用 suffixMin 数组预处理来减少比较次数，但交换操作破坏了 suffixMin 的正确性，且仍然不稳定
应用场景
选择排序由于效率低下，实际应用中很少直接使用，但作为教学示例非常重要：
- 理解基础排序思想
- 作为优化起点（插入排序、冒泡排序都是其改进）
- 理解算法稳定性和优化限制