选择排序算法的Java实现¶
什么是选择排序？¶
选择排序（Selection Sort）是一种简单直观的排序算法。它的核心思想就像我们整理扑克牌：每次从一堆未排序的牌中，挑出最小（或最大）的那张，放到已经排好序的牌堆末尾。重复这个过程，直到所有牌都排好序。
选择排序的基本思路¶
假设我们有一个数组 arr，需要将其从小到大排序。步骤如下：
1. 外层循环：遍历数组的每一个位置 i（从0开始），这个位置表示“已排序部分的末尾”，接下来要确定第 i 个位置的元素。
2. 内层循环：在未排序部分（从 i+1 到数组末尾）中，找到最小元素的索引 minIndex。
3. 交换元素：将 i 位置的元素与 minIndex 位置的元素交换，此时 i 位置的元素已确定为未排序部分的最小值。
4. 重复：外层循环继续，直到所有元素都排好序。
Java代码实现¶
下面是选择排序的Java代码，附带详细注释：
public class SelectionSort {
// 选择排序方法
public static void selectionSort(int[] arr) {
int n = arr.length; // 数组长度
// 外层循环：遍历每一个需要确定的位置i（从0到n-1）
for (int i = 0; i < n - 1; i++) {
// 初始化最小值的索引为当前位置i
int minIndex = i;
// 内层循环：在未排序部分（i+1到n-1）中找最小值
for (int j = i + 1; j < n; j++) {
// 如果当前元素arr[j]比minIndex位置的元素小，更新minIndex
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 将未排序部分的最小值与i位置元素交换
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
// 测试方法
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("排序前的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
selectionSort(arr); // 调用选择排序
System.out.println("\n排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
代码详解¶
-
外层循环：
for (int i = 0; i < n - 1; i++)
- 变量i表示“已排序部分的末尾位置”。当i = 0时，需要确定第0个位置的元素；当i = n-2时，只剩最后一个元素未排序，循环结束。 -
内层循环：
for (int j = i + 1; j < n; j++)
- 在内层循环中，从i+1开始遍历到数组末尾，寻找未排序部分的最小值。 -
找最小值：
if (arr[j] < arr[minIndex]) { minIndex = j; }
- 变量minIndex始终记录当前找到的最小值的索引。初始时假设i位置是最小值，若后续发现更小的元素，则更新minIndex。 -
交换元素：
temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;
- 将i位置的元素与未排序部分的最小值交换，此时i位置的元素已确定为最小值，进入下一轮循环。
排序过程示例¶
以数组 {64, 25, 12, 22, 11} 为例，逐步演示排序过程：
- 初始数组：
[64, 25, 12, 22, 11] - 第1轮（i=0）：内层循环找
[1,2,3,4]中的最小值。最小元素是11（索引4），交换后数组变为[11, 25, 12, 22, 64]。 - 第2轮（i=1）：内层循环找
[2,3,4]中的最小值。最小元素是12（索引2），交换后数组变为[11, 12, 25, 22, 64]。 - 第3轮（i=2）：内层循环找
[3,4]中的最小值。最小元素是22（索引3），交换后数组变为[11, 12, 22, 25, 64]。 - 第4轮（i=3）：内层循环找
[4]中的最小值（只有64），无需交换，数组保持不变。
最终排序结果：[11, 12, 22, 25, 64]。
时间复杂度¶
选择排序的时间复杂度为 O(n²)（n为数组长度）。无论数组初始状态如何，内层循环都需要执行约n²/2次比较，因此适合小规模数据排序。
总结¶
选择排序的核心是“每次选最小值”，通过交换元素逐步构建有序数组。它的逻辑简单，代码易实现，适合初学者理解排序算法的基础思想。通过上述示例和代码，相信你已经掌握了选择排序的Java实现方法！