1.排序思路
选择排序算法重复这样的过程，分别将每个特定的值放到排好序的最终位置，从而完成一组值的排序。换句话说，对于表中的每个位置，算法选择应该处在那个位置的值，并将它放置到位。
选择排序算法的一般策略是：扫描整个表，找到最小值。将这个值与表中第一个位置的值相交换。扫描余下的表（除第一个元素之外的所有值），查找最小值，将这个值与表第二个位置的值相交换。扫描余下的表（除第一个和第二个值之外的所有值），查找最小值，将这个值与表的第三个位置的值相交换。对表中每个位置继续这个过程。完成时，表中排序完毕。
2.示例图
选择排序过程如下图所示。
选择排序示例图
3.代码实现
public static void selectSort(int arr[]){
int temp;
for(int i = 0;i < arr.length-1; i ++){//有N个元素只需比较N-1次
int min = i;//记住初始位置
for(int j = i+1; j < arr.length; j ++){//在 [i+1,arr.length) 中选最小元素，注意这里的i+1和arr.lenth均为元素下标
if(arr[j] < arr[min])
min = j;//min记下目前找到的最小元素的下标
if(min != i){ //每趟比较中元素之间只进行一次交换，即元素移动3次。
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
}
public static void main(String[] args) {
int array[] = {3,9,6,1,2};
System.out.println("排序之前：");
for(int element : array){
System.out.print(element+" ");
}
selectSort(array);
System.out.println("\n排序之后");
for(int element : array){
System.out.print(element+" ");
}
}
}
4.算法分析
1.在选择排序中，无论元素的初始序列如何，都要进行 (n-1)+(n-2)+(n-3)+....+1 = n*(n-1)/2 = O(n2)次比较，所以时间复杂度为O(n2) n为元素个数
2.当元素的初始序列为正序时，移动次数为0，而当元素的初始序列为反序时，总的移动次数为：3总趟数，即Mmax = 3(n-1)
3.在直接选择排序中只使用了i,j,min这3个辅助元素，与问题规模无关，所以空间复杂度为O(1).
4.当元素序列类似[8,5,8,1]时，在第一趟比较中第一个元素8和最后个元素1进行了交换，元素中的两个8的相对位置发生了改变，所以直接选择排序是一种不稳定排序。
参考文章：数据结构之选择排序--简单选择排序
