选择排序
一句话总结
选择排序是最简单朴素的排序算法，时间复杂度 O(n²)，不是稳定排序，其他基础排序算法都是基于选择排序的优化。
核心要点
1. 算法思路
先遍历数组找到最小值，与第一个元素交换；再遍历剩余部分找到次小值，与第二个元素交换；以此类推直到整个数组有序。
2. 时间复杂度与优化尝试
- 时间复杂度：O(n²)，嵌套循环执行 n²/2 次
- 特点：即使数组已有序，仍执行相同次数，原始数据有序度不影响时间复杂度
- 优化尝试：尝试用 suffixMin 数组预计算后缀最小值，但因交换操作导致 nums 变化，预计算失效，无法优化
3. 排序稳定性
- 不是稳定排序：交换操作会打乱相同元素的相对位置
- 原因：第一次寻找最小值时就可能交换，破坏相同元素的原始顺序
- 优化思考：作者提出思考方向，后续排序算法会尝试解决
基本原理
选择排序的核心：每次选择未排序部分的最小值，放到已排序部分的末尾。
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²) | 嵌套循环，等差数列求和 n²/2 |
| 空间 | O(1) | 原地排序，仅用常数个变量 |
代码实现
关键代码片段
// 计算后缀最小值的尝试（虽然最终无法用于优化选择排序）
int[] suffixMin = new int[nums.length];
suffixMin[nums.length - 1] = nums[nums.length - 1];
for (int i = nums.length - 2; i >= 0; i--) {
suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);
}
实现要点
- 使用
sortedIndex作为已排序/未排序的分割线 - 每次遍历未排序部分找最小值索引
- 交换最小值与分割线位置的元素
- 分割线后移一位
对比分析
| 维度 | 选择排序 | 说明 |
|---|---|---|
| 时间复杂度 | O(n²) | 基础排序算法中最慢的一档 |
| 空间复杂度 | O(1) | 原地排序 |
| 稳定性 | 不稳定 | 交换操作破坏相同元素相对顺序 |
| 适用场景 | 小规模数据 | 大规模数据应使用更高效的排序算法 |
应用场景
- 小规模数据排序
- 教学演示排序算法基础思想
- 作为更复杂排序算法的对比基准
验证方法
- 可通过 LeetCode 912「排序数组」验证（但会超时，仅逻辑正确）
- 可通过简单测试代码验证正确性
相关题目
| 平台 | 题目 | 难度 |
|---|---|---|
| LeetCode | 912. Sort an Array | Medium |
| 力扣 | 912. 排序数组 | 中等 |
相关概念
相关实体
- labuladong：算法学习平台 labuladong.online 作者
总结
选择排序虽然简单，但蕴含了重要的算法思维：通过尝试优化（如 suffixMin 预计算）理解算法的局限性。交换操作既导致不稳定，也阻碍了优化。后续排序算法（如插入排序、冒泡排序、快速排序等）将在选择排序的基础上改进。