如果你面前有一堆大小不一的苹果，要求你按从小到大的顺序排成一排，你会怎么做？绝大多数人的第一反应是：先在整堆苹果里挑出最小的，放在第一个；然后在剩下的苹果里再挑出最小的，放在第二个……依此类推。
恭喜你，这其实就是选择排序的核心思想！
核心思想：简单粗暴的“挑兵挑将”
选择排序的逻辑非常纯粹，它将数组分为两部分：已排序区间和未排序区间。初始状态下，已排序区间为空，所有元素都在未排序区间。
它的运行步骤可以概括为以下三步：
1、在未排序区间中，先假设第一个元素是最小值，并记录它的索引。
2、遍历剩下的未排序元素，如果发现有比假设的最小值还小的元素，就更新最小值的索引。
3、遍历结束后，将找到的“真正最小值”与未排序区间的第一个元素交换位置。此时，已排序区间增加了一个元素，未排序区间减少了一个元素。
4、重复以上步骤，直到所有元素都进入已排序区间。
代码实现
选择排序的代码实现非常清晰，主要由两个嵌套的 for 循环组成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| public class SelectionSortDemo {
public static void main(String[] args) {
int[] arr = {29, 10, 14, 37, 13};
System.out.println("排序前：");
printArray(arr);
selectionSort(arr);
System.out.println("排序后：");
printArray(arr);
}
/**
* 选择排序核心方法
* @param arr 待排序数组
*/
public static void selectionSort(int[] arr) {
int n = arr.length;
// 外层循环：控制需要放置最小元素的位置，即已排序区间的边界
for (int i = 0; i < n - 1; i++) {
// 假设当前位置 i 的元素是未排序区间中的最小值
int minIndex = i;
// 内层循环：在未排序区间 [i+1, n-1] 中寻找真正的最小值索引
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
// 发现更小的元素，更新 minIndex
minIndex = j;
}
}
// 如果真正的最小值索引不是一开始假设的 i，则进行交换
if (minIndex != i) {
swap(arr, i, minIndex);
}
}
}
/**
* 交换数组中两个元素的方法
*/
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 打印数组辅助方法
*/
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
|
核心代码解析：
1、外层循环 (i)： 代表了当前正在为第 i 个位置寻找正确的（也就是最小的）元素。因为当只剩最后一个元素时，它自然就是最大的，所以外层循环只需要走到 n - 1 即可。
2、内层循环 (j)： 从 i + 1 开始，一直扫描到数组末尾。它的唯一任务就是“找茬”——看看有没有比当前 arr[minIndex] 还要小的元素。
3、避免无意义的交换： 在交换前加上 if (minIndex != i) 这个判断是个好习惯。如果未排序区间的第一个元素本身就是最小值，我们就不需要多此一举去交换它了。
总结
在实际的软件工程中，由于 $O(N^2)$ 的时间复杂度，我们很少在大量数据的场景下使用选择排序。但它作为算法学习的“垫脚石”却非常优秀：它不需要复杂的递归，不需要额外的内存，且逻辑极其贴合人类思维。掌握选择排序，能帮我们更好地理解“双重循环”在数组操作中的应用，也为我们后续学习更复杂的算法打下坚实的基础。