思路：
- 数组区分已排序区域和未排序区域
- 每次从未排序区域找到最小的元素，通过和未排序区域第一个元素交换位置，把它放到已排序区域的末尾
步骤：
- 进行 数组长度-1 轮比较
- 每轮找到未排序区最小值的小标
- 如果最小值的下标非未排序区第一个，进行交换。此时未排序区第一个则变为已排序区最后一个
- 进行下一轮找未排序区最小值下标，直到全部已排序
代码：
package constxiong.interview.algorithm;/** * 选择排序 * @author ConstXiong * @date 2020-04-09 12:25:12 */public class SelectionSort { public static void main(String[] args) { int [] array = {33, 22, 1, 4, 25, 88, 71, 4}; selectionSort(array); } /** * 选择排序 * @param array */ public static void selectionSort(int[] array) { print(array); //进行 数组长度-1 轮比较 int minIndex; for (int i = 0; i <array.length-1; i++) { minIndex = i;//取未排序区第一个数的下标 for (int j = i+1; j <array.length; j++) { if (array[j] <array[minIndex]) { //找到未排序区域最小值的下标 minIndex = j; } } //找到的最小值是否需要挪动 if (i != minIndex) { int temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; } print(array); } } /** * 打印数组 * @param array */ private static void print(int[] array) { for(int i : array) { System.out.print(i + " "); } System.out.println(); }}打印：
33 22 1 4 25 88 71 4 1 22 33 4 25 88 71 4 1 4 33 22 25 88 71 4 1 4 4 22 25 88 71 33 1 4 4 22 25 88 71 33 1 4 4 22 25 88 71 33 1 4 4 22 25 33 71 88 1 4 4 22 25 33 71 88 特征：
- 空间复杂度为 O(1)，是原地排序算法
- 最好情况时间复杂度为 O(n2)。即使是有序数组，也需要经过 n-1 轮找未排序区最小值下标
- 最坏情况时间复杂度为 O(n2)
- 平均情况时间复杂度为 O(n2)
- 非稳定排序，即排序后不能保证两个相等值的前后顺序未变。如：4，8，4，2，9。第一轮找到最小元素 2，跟第一个 4 交换位置，直到排序完成第一个 4 排在第二个 4 后面
