选择排序(Selection sort) 是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小(大)元素，然后放到已排序的序列的末尾。以此类推，直到没有待排序的数据元素。
算法特性
- 稳定性
选择排序是不稳定的排序算法。
- 时间复杂度
选择排序的时间复杂度均为 O(n^2)，在所有情况下都是相同的，无论是最好、最坏还是平均情况。
- 空间复杂度
选择排序是原地排序算法，不需要额外的的存储空间，其空间复杂度为O(1)。
算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。
动画演示
选择排序.gif
代码实现
Java代码:
public static int[] selectionSort(int[] sourceArray) {
if (sourceArray == null || sourceArray.length < 2) {
return sourceArray;
}
int[] array = Arrays.copyOf(sourceArray, sourceArray.length);
// 总共要经过n-1轮
for (int i = 0; i < array.length - 1; i++) {
int min = i;
for (int j = i + 1; j < array.length; j++) {
if (array[min] > array[j]) {
// 记录目前能找到的最小值元素的下标
min = j;
}
}
// 将找到的最小值和i位置所在值进行交换
if (min != i) {
swap(array, i, min);
}
}
return array;
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
