1. 简介
本文我们将学习 选择排序（Selection Sort），并通过 Java 实现它，同时分析其性能表现。
选择排序是一种简单但效率不高的排序算法，适用于小规模数据集。它通过重复“找出未排序部分的最小元素并放到前面”的方式逐步构建有序序列。
2. 算法概述
选择排序的基本思想是：
- 从数组的第一个元素开始，扫描整个数组，找出最小的元素；
- 将该最小元素与第一个元素交换位置；
- 接着从第二个元素开始重复上述过程，找出剩余部分中最小的元素，并与第二个元素交换；
- 依此类推，直到倒数第二个元素。
最终，最后一个元素自然就在正确位置上，整个数组完成排序。
✅ 一句话总结：每次找最小，放到正确位置，逐步构建有序序列。
如果是降序排列，则每次找的是最大元素。
2.1. 示例演示
我们以一个未排序数组为例：
int[] arr = {5, 4, 1, 6, 2};
第一轮迭代：
- 当前位置：索引 0，值为 5；
- 扫描剩余元素，找到最小值 1；
- 与索引 0 位置的元素交换。
结果数组变为：
{1, 4, 5, 6, 2}
比较次数：4次
第二轮迭代：
- 当前位置：索引 1，值为 4；
- 扫描剩余元素，找到最小值 2；
- 与索引 1 位置的元素交换。
结果数组变为：
{1, 2, 5, 6, 4}
比较次数：3次
第三轮迭代：
- 当前位置：索引 2，值为 5；
- 找到最小值 4；
- 与索引 2 位置交换。
结果：
{1, 2, 4, 6, 5}
比较次数：2次
第四轮迭代：
- 当前位置：索引 3，值为 6；
- 找到最小值 5；
- 与索引 3 位置交换。
最终排序结果：
{1, 2, 4, 5, 6}
比较次数：1次
3. Java 实现
下面是使用双重循环实现的选择排序代码：
3.1. 升序排序
public static void sortAscending(final int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minElementIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minElementIndex] > arr[j]) {
minElementIndex = j;
}
}
if (minElementIndex != i) {
int temp = arr[i];
arr[i] = arr[minElementIndex];
arr[minElementIndex] = temp;
}
}
}
3.2. 降序排序
public static void sortDescending(final int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int maxElementIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[maxElementIndex] < arr[j]) {
maxElementIndex = j;
}
}
if (maxElementIndex != i) {
int temp = arr[i];
arr[i] = arr[maxElementIndex];
arr[maxElementIndex] = temp;
}
}
}
⚠️ 注意：以上实现都使用了“选择最小/最大”+“交换”的方式，避免频繁移动元素。
如果想更灵活地控制排序方式，可以结合 Java 的 Comparator 接口实现泛型版本。
4. 性能分析
4.1. 时间复杂度
我们来计算一下总共做了多少次比较：
- 第一轮比较 n-1 次；
- 第二轮比较 n-2 次；
- ...
- 最后一轮比较 1 次。
总共比较次数为：
(n-1) + (n-2) + ... + 1 = (n-1)*n / 2
简化后为：
O(n²)
✅ 所以选择排序的时间复杂度是 **O(n²)**，不管输入数据是否已经部分有序，都需要进行这么多轮比较。
4.2. 空间复杂度
选择排序只使用了一个临时变量用于交换元素，因此空间复杂度为：
O(1)
✅ 是一个原地排序算法，占用空间非常小。
5. 总结
选择排序的优点：
- ✅ 实现简单；
- ✅ 原地排序，空间占用小；
- ✅ 不依赖数据分布，适用于小数据集。
缺点：
- ❌ 时间复杂度为 O(n²)，性能较差；
- ❌ 无法提前终止，即使数组已经有序，也要完成所有遍历；
- ❌ 不稳定排序（相同元素的位置可能改变）。
在实际开发中，如果你面对的是大数据量，建议使用更高效的排序算法，如快速排序、归并排序或 Java 自带的 Arrays.sort()。
完整代码示例可参考：GitHub 示例仓库（示例链接，非真实地址）