一、算法原理
选择排序将数组分为已排序区间和未排序区间，每次选择未排序区间的最小元素，将它放到已排序区间末尾。一次选择会让一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序。
示例：使用选择排序对数组 arr = [4，5，6，3，2，1] 从小到大排序。
第1次选择：
第2次选择：
第3次选择：
第4次选择：
第5次选择：
第6次选择：
二、选择排序优化
思路：选择未排序区间的最小元素，不需要出现小于当前元素的就交换，可以只记住下标，本次选择完成之后再交换，这样每一次选择只需要交换一次，省去了很多次无效交换。
三、代码实现
/**
* 选择排序，时间复杂度 O(n^2)，空间复杂度 O(1)，不稳定
*
* @param arr 待排序数组
*/
public static void selectSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0, len = arr.length; i < len - 1; i++) {
int min = i;
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
swap(arr, min, i);
}
}
}
private static void swap(int[] arr, int i, int j) {
if (i == j) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}四、算法评价
4.1 时间复杂度
选择排序的最好、最坏、平均时间复杂度都是 O(n2)，因为不论数组原来是否有序，每次都要从未排序区间找到最小值，而最小值只能通过全部比较一次才能得到。
4.2 空间复杂度
选择排序只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。
4.3 稳定性
选择排序是一种不稳定的排序算法，因为每次都要从未排序区间找最小值，并和前面的元素交换位置，破坏了稳定性。比如，数组 [5，6，5，2，3]，第一次找到的最小元素是 2，与第1个 5 交换位置，这样第1个 5 和第2个 5 的顺序已经改变了。