【基础篇】3、选择排序

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

一、选择排序是什么？二、代码实现三、选择排序的稳定性、复杂度及适用场景

选择排序是一种简单直观的排序算法。第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，继续放在起始位置知道未排序元素个数为0。
下图为选择排序的动态图：

public static void selectionSort(int[] arr) {
	
		if (arr == null || arr.length < 2) {
			return;
		}
		
		for (int i = 0; i < arr.length - 1; i++) { 
			//min变量保存该趟比较过程中，最小元素所对应的索引，
			//先假设前面的元素为最小元素
			int minIndex = i;
			
			for (int j = i + 1; j < arr.length; j++) {
				//如果后面的元素小，将后面元素的索引极为最小值的索引
				if(arr[j] < arr[minIndex]) {
					minIndex = j;
				}
			}
			//然后交换此次查找到的最小值和原始的最小值
			swap(arr, i, minIndex);
		}
	}
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

在选择排序中，每趟都会选出最大元素与最小元素，然后与两端元素交换，此时，待排序序列中如果存在与原来两端元素相等的元素，稳定性就可能被破坏。