选择排序 Java 实现 + 完整思路解析

一、核心思路选择排序思想 将数组分为「已排序区间」和「未排序区间」。初始已排序区间为空整个数组属于未排序区间每一轮在未排序区间找到最小值下标把最小值和未排序区间第一个元素交换此时未排序区间第一个元素归入已排序区间重复执行直到所有元素有序。特点总结面试常考时间复杂度最好 / 最坏 / 平均 \(O(n^2)\)无论数组是否有序都要遍历查找最小值无法优化提前退出不稳定排序相等元素相对位置可能改变交换次数很少最多 n-1 次交换对比冒泡排序大量交换数据交换成本高的场景有优势二、完整代码实现java运行public class SelectSort { public static void main(String[] args) { int[] arr {6, 3, 8, 2, 9, 1}; System.out.println(排序前); printArray(arr); selectSort(arr); System.out.println(排序后); printArray(arr); } /** * 选择排序 升序实现 * param arr 待排序数组 */ public static void selectSort(int[] arr) { int len arr.length; // 外层循环控制未排序区间起始位置 // i 代表未排序区间第一个下标最终到 len-2 即可 for (int i 0; i len - 1; i) { // 假设当前i位置是最小值下标 int minIndex i; // 内层循环从i1开始寻找未排序区间最小值下标 for (int j i 1; j len; j) { if (arr[j] arr[minIndex]) { minIndex j; } } // 如果最小值下标不是i说明需要交换 if (minIndex ! i) { int temp arr[i]; arr[i] arr[minIndex]; arr[minIndex] temp; } } } // 打印数组工具方法 public static void printArray(int[] arr) { for (int num : arr) { System.out.print(num ); } System.out.println(); } }三、手动推演示例数组[6, 3, 8, 2, 9, 1]i0未排序区间 [0~5]找到最小值下标 5数值 1交换下标 0 和 5 →[1, 3, 8, 2, 9, 6]i1未排序区间 [1~5]最小值下标 13无需交换i2未排序区间 [2~5]最小值下标 32交换下标 2 和 3 →[1, 3, 2, 8, 9, 6]持续循环直到全部有序。四、关键对比面试区分冒泡 选择冒泡排序相邻两两比较不合适立刻交换每轮把最大值 “浮上去”选择排序先找到最值下标一轮结束只交换一次拓展想要降序排序只需要修改判断条件if (arr[j] arr[maxIndex])寻找最大值放到前面。