数据结构与算法 / 系统课时
选择排序
选择排序
选择排序通过反复寻找未排序区间中的最小元素,并把它放到当前区间起点,完成原地升序排列。本课将实现一个可运行的 Java 版本,并准确统计比较次数与数据交换次数。
学习目标
- 说明选择排序每一轮如何缩小未排序区间。
- 使用 Java 实现原地选择排序并验证结果。
- 分析比较次数、交换次数、稳定性和复杂度。
问题定义
给定一个长度为 n 的数组,选择排序把数组划分为“已排序区间”和“未排序区间”。第 i 轮在下标 i 到 n - 1 中寻找最小值,再将其交换到下标 i。完成一轮后,已排序区间向右扩展一个元素。

核心原理
选择排序的关键循环不变式是:第 i 轮开始时,下标 0 到 i - 1 已经包含全局最小的 i 个元素,并且按升序排列。第 0 轮前缀为空。每轮把剩余最小项放在前缀末尾,已确定的项保持不动。交换不增删记录。最后剩一项时它必在正确位置,空数组或单元素直接满足要求。
对于长度为 n 的数组,各轮比较次数依次为 n - 1、n - 2,直到 1,总比较次数固定为:
无论输入是否接近有序,基础选择排序都必须完成这些比较。交换次数最多为 n - 1;当最小元素已就位时跳过交换。n≥1 时最多 n−1 次,n=0 时为 0。一次交换包含两次数组写入,另有暂存变量赋值。
这个交换式实现不稳定。例如 [2A, 2B, 1C] 首轮交换 2A 与 1C,得到 [1C, 2B, 2A],两条键为 2 的记录顺序反转。可改为抽出第一个最小项并把中间记录右移,代价是移动次数可能变成平方级。它的额外空间复杂度为 O(1),平均和最坏时间复杂度均为 O(n^2)。
完整可运行示例
下面的程序在排序时统计比较次数和真实交换次数。将代码保存为 SelectionSortDemo.java。
import java.util.Arrays;
public class SelectionSortDemo {
public static void main(String[] args) {
int[] values = {64, 25, 12, 22, 11};
SortStats stats = selectionSort(values);
System.out.println("排序结果: " + Arrays.toString(values));
System.out.println("比较次数: " + stats.comparisons);
System.out.println("交换次数: " + stats.swaps);
}
static SortStats selectionSort(int[] values) {
long comparisons = 0;
int swaps = 0;
for (int i = 0; i < values.length - 1; i++) {
int minIndex = i;
// 在未排序区间中寻找最小元素的下标。
for (int j = i + 1; j < values.length; j++) {
comparisons++;
if (values[j] < values[minIndex]) {
minIndex = j;
}
}
// 最小元素已经就位时,不进行无意义交换。
if (minIndex != i) {
int temp = values[i];
values[i] = values[minIndex];
values[minIndex] = temp;
swaps++;
}
}
return new SortStats(comparisons, swaps);
}
static class SortStats {
final long comparisons;
final int swaps;
SortStats(long comparisons, int swaps) {
this.comparisons = comparisons;
this.swaps = swaps;
}
}
}运行命令
javac -encoding UTF-8 SelectionSortDemo.java
java SelectionSortDemo预期输出
排序结果: [11, 12, 22, 25, 64]
比较次数: 10
交换次数: 3复杂度与适用场景
| 指标 | 结论 |
|---|---|
| 最好、平均、最坏时间复杂度 | Θ(n²),比较次数与排列无关 |
| 额外空间复杂度 | O(1) |
| 稳定性 | 通常不稳定 |
| 数据移动次数 | 最多 n - 1 次交换 |
选择排序的优势不是比较少,而是数据移动少。当元素交换成本明显高于比较成本、数据规模较小且不要求稳定性时,它比频繁交换相邻元素的算法更有吸引力。
Tips
- 使用
minIndex记录位置,不要在扫描过程中立即交换,否则会破坏“一轮只确定一个位置”的结构。 - 只有
minIndex != i时才交换,统计结果才能反映真实数据移动次数。 - 调试时可在每轮结束后打印数组,检查已排序区间是否持续扩大。
常见错误
1. 未排序区间边界写错
若内层循环从 0 开始,每一轮都会重复扫描已排序区间。正确范围应从 i + 1 开始,并一直比较到数组末尾。
2. 把赋值次数当作交换次数
一次交换通常需要三次赋值,但算法分析中的“交换次数”应按一次元素位置互换计数。统计口径必须在代码和结论中保持一致。
本课练习
- 将示例数组改为已经升序的数组,验证比较次数是否仍为
n(n - 1) / 2,并观察交换次数。 - 修改程序,使其按降序排列,同时保持比较次数和交换次数统计正确。
本课总结
- 选择排序每轮从未排序区间选择最小元素,并固定一个最终位置。
- 比较次数与输入顺序无关,始终为
n(n - 1) / 2。 - 算法原地执行且移动次数少,但时间复杂度为
O(n^2),通常不稳定。
下一课预告
下一课将学习“冒泡排序”,重点观察相邻元素交换如何把较大元素逐轮推向数组末端,并实现提前终止优化。