Selection Sort 选择排序
选择排序（Selection Sort）的思路是遍历待排序的数组，将当前位置视为最小值的索引。在剩余未排序部分中，循环并比较元素，找到最小值，并更新最小值的索引。将找到的最小值与当前位置交换。重复这两个循环，直到所有元素都被排序。
具体的插入排序算法步骤如下：
- 遍历待排序的数组，将当前位置视为最小值的索引。
- 在剩余未排序部分中，逐个比较元素，找到最小值，并更新最小值的索引。
- 将找到的最小值与当前位置交换。
- 重复步骤2-3，直到所有元素都被排序。
public class Sort { public static void insertionSort(int[] array) { int n = array.length; for (int i = 0; i < n-1; i++) { int minIndex = i; // 找到剩余未排序部分中的最小值索引 for (int j = i + 1; j < n; j++) { if (array[j] < array[minIndex]) { minIndex = j; } } // 将找到的最小值与当前位置的元素交换位置 int temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; } } public static void main(String[] args) { int[] array = {5, 2, 8, 12, 1, 6}; insertionSort(array); System.out.println("排序结果："); for (int num : array) { System.out.print(num + " "); } } }
选择排序的时间复杂度为O(n^2)，其中n是待排序列表的元素个数。
空间复杂度为O(1)，因为算法只需要常数级的额外空间来存储索引和临时变量。
由于选择排序在每次遍历中只进行一次交换，因此其交换操作相对较少，适用于较小规模的数组排序。然而，对于大规模数据集，选择排序的性能相对较差，更高效的排序算法如快速排序或归并排序更为适用。
