J019_选择排序

一、排序算法

排序过程和排序原理如下图所示：

二、代码实现

package com.itheima.sort;import java.util.Arrays;public class SelectSort {public static void main(String[] args) {int[] arr = {5, 4, 3, 1, 2};//选择排序for (int i = 0; i < arr.length - 1; i++) {for (int j = i + 1; j < arr.length; j++) {//假设i位置的数字是最小的，将i位置的数字依次与i以后的每个位置的数字做比较//如果i位置的数字大于后面的数字，则将两数的位置进行交换if (arr[i] > arr[j]) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}}}System.out.println(Arrays.toString(arr));}
}

三、排序优化

由于在每轮比较的过程中，两两数字做对比，如果指定位置的最小数比与做对比的数字大，就要交换两数的位置，这样的话交换次数过多会影响系统的性能。

优化方案：在每轮中进行两数比较之前，都记录一个最小数的下标，在每轮比较完成后，将最小数的下标记到存最小数下标的变量中，然后再去判断是否需要做交换即可。

代码实现如下：

package com.itheima.sort;import java.util.Arrays;public class SelectSort1 {public static void main(String[] args) {int[] arr = {5, 4, 11, 32, 111, 1, 3, 2};for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;for (int j = i + 1; j < arr.length; j++) {if (arr[minIndex] > arr[j]) {minIndex = j;}}if (arr[i] > arr[minIndex]) {int tmp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = tmp;}}System.out.println(Arrays.toString(arr));}
}