【算法-选择排序】挑挑拣拣，排出顺序——选择排序入门
什么是选择排序？
选择排序是一种比较简单直接的排序方式。想象你在打散一副牌，想按照大小顺序从小到大排列这些牌。你会怎么做？可能会先找出最小的那张，放在最前面，然后在剩下的牌里找第二小的，依次类推，这就是选择排序的基本思路！
在程序中，选择排序的操作流程也类似：它逐步将未排序的部分中最小的元素找到，放到前面的位置，直到整个数组有序。
选择排序的操作步骤
为了更直观，我们来看看每一步是如何进行的：
步骤1：找到未排序部分中的最小值
首先，从一堆数字中找到最小的那个。这就像玩扑克牌时，眼睛在一张张扫过，看看哪一张最小。
步骤2：把最小值放到正确的位置
找到最小值之后，就把它交换到最前面的位置，让它“坐在”已经排好序的队伍的最前面。剩下的数字依然是乱的，我们继续重复这个过程。
步骤3：重复以上操作，直到所有数字排好
这个操作会一直重复，下一步我们会从第二个位置开始，再找出剩余部分的最小值，放在第二位。这样一轮一轮地把最小值一个个找出来，依次放到前面，最终就会得到一个按从小到大的顺序排列的列表！
图解选择排序
选择排序
假设我们有以下一个无序数组：[29, 10, 14, 37, 13]
我们用选择排序来一步步将它排好顺序：
-
第一轮：
- 从[29, 10, 14, 37, 13]中找最小值。
- 发现最小的是10，把10放到第一个位置。
- 交换后数组变成：[10, 29, 14, 37, 13]
-
第二轮：
- 从[29, 14, 37, 13]中找最小值。
- 最小的是13，把13放到第二个位置。
- 交换后数组变成：[10, 13, 14, 37, 29]
-
第三轮：
- 从[14, 37, 29]中找最小值。
- 最小的是14，已经在正确的位置，无需交换。
- 数组保持不变：[10, 13, 14, 37, 29]
-
第四轮：
- 从[37, 29]中找最小值。
- 发现最小的是29，交换到第四个位置。
- 交换后数组变成：[10, 13, 14, 29, 37]
到这里，整个数组从小到大排列完成：[10, 13, 14, 29, 37]
代码
public class SelectionSortExample {public static void selectionSort(int[] arr) {int n = arr.length; // 获取数组长度// 遍历整个数组，逐步找到每个位置上的最小元素for (int i = 0; i < n - 1; i++) {// 假设当前位置的元素是最小的int minIndex = i;// 从当前元素后面开始寻找真正的最小值for (int j = i + 1; j < n; j++) {// 如果找到更小的元素，则更新minIndexif (arr[j] < arr[minIndex]) {minIndex = j;}}// 将找到的最小元素与当前位置的元素交换// 这里的交换确保了当前索引i位置是最小的元素if (minIndex != i) { // 仅在必要时交换int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}// 打印当前排序的进度，便于观察每一轮的结果System.out.print("第 " + (i + 1) + " 轮排序结果：");printArray(arr);}}// 辅助方法，用于打印数组内容public static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}// 主方法，用于测试选择排序public static void main(String[] args) {int[] arr = {29, 10, 14, 37, 13}; // 初始化无序数组System.out.print("初始数组：");printArray(arr);// 进行选择排序selectionSort(arr);System.out.print("最终排序结果：");printArray(arr);}
}
代码说明
- 外层循环：
for (int i = 0; i < n - 1; i++)，每次确定数组的一个位置。它从第一个位置开始，一直到倒数第二个位置（最后一个位置不需要再找，因为此时已排好序）。 - 假设最小值：
int minIndex = i;，假设当前位置是最小值的索引。 - 内层循环：
for (int j = i + 1; j < n; j++)，从当前位置的下一个元素开始找出真正的最小值。 - 更新最小值索引：
if (arr[j] < arr[minIndex]) { minIndex = j; }，找到比当前最小值更小的元素后，更新minIndex。 - 交换操作：
if (minIndex != i)，交换当前元素和找到的最小元素的位置，以确保当前索引i上放的是该轮的最小值。 - 打印当前排序进度：在每轮结束时调用
printArray(arr);打印数组内容，便于观察排序过程。
选择排序的特点
- 简单直观：一步步从未排序部分挑出最小的元素，放到前面的已排序区域。
- 适合小数据量：虽然简单，但是时间复杂度是 O(n²)，当数据量大时效率较低，所以通常在小数据量的情况使用。
- 内存占用低：只需要极少的额外空间，是一种原地排序算法。
什么时候适合使用选择排序？
选择排序适合在对数据要求不高的小型场景下使用。例如，小批量数据的排序或对稳定性要求不高的简单排序场景。