思想
选择排序，顾名思义，就是每次从待排数组中选择最大火最小的一个出来，这里我们以升序来举例，每次从待排序的数组中选出最小的放到待排序数组的第一位。 这样原来的数组就会有两部分，前面一部分是已经排好序的，后面一部分是待排序的数组。
由此看来，选择排序的一个优点是不需要开辟额外的存储空间。
再说的简单一点，就是将数列看做一群学生，对着他们说你们最矮的出列，站到最左边，然后这个孩子不动，接着对剩下的孩子说，你们最矮的出列，挨着第一个孩子旁边站， 直到所有的还在都出列。
举例
例如要对 6 7 4 1 5 9 进行升序的选择排序操作，过程如下
从第一个选择最小的开始，我们会比较第一个元素和剩余元素的大小，然后进行交换，将最小的放到第一位，直到最后比较最后剩下的两个数，确定位置， 一共会比较n-1次，所以一共有n-1趟，这个趟也就是外循环。
所以
- 第一趟
第一趟找到最小的数是1，将1和6进行交换
| 交换前 | 6 | 7 | 4 | 1 | 5 | 9 |
| 交换后 | 1 | 7 | 4 | 6 | 5 | 9 |
- 第二趟
第一趟找到最小的数是1，将1和6进行交换之后，有序数组是1，无序数组是7 4 6 5 9，从无序数组中选出最小的4，放到有序数组之后，也就是与无序数组的首位进行交换
| 交换前 | 1 | 7 | 4 | 6 | 5 | 9 |
| 交换后 | 1 | 4 | 7 | 6 | 5 | 9 |
- 第三趟
继续寻找无序数组的最小数，是5，与7进行交换
| 交换前 | 1 | 4 | 7 | 6 | 5 | 9 |
| 交换后 | 1 | 4 | 5 | 6 | 7 | 9 |
- 第四趟
继续寻找无序数组的最小数，是6，不交换
| 交换前 | 1 | 4 | 5 | 6 | 7 | 9 |
- 第五趟
继续寻找无序数组的最小数，是7，不交换
| 交换前 | 1 | 4 | 5 | 6 | 7 | 9 |
至此，n-1趟外循环的比较结束。
那么，每一次是如何选出最小的树呢？
例如，开始第一个数是6，我们假定他是最小的，我们就拿6去和7比较，6<7，不变，接着用6和4比较，6>4，就将最小的数变成4，然后和1比较，1<4，最小的数就 变成1，接着往后比较，5和9都比1大，所以最小的数是1。
可以看到，在找出最小数的比较中，循环的次数和无序数组的长度有关，假设无序数组是m，比较的次数就是m-1。
代码
package test;
import java.nio.channels.SelectableChannel;
import java.util.Arrays;
public class SlecteSort {
public static void main(String[] args) {
SlecteSort slecteSort = new SlecteSort();
int [] a= {5,2,8,4,9,1};
slecteSort.slectedSort(a);
System.out.println(Arrays.toString(a));
}
public void slectedSort(int [] a){
// 如果数组为空或者个数是0，就返回
if (a == null || a.length == 0) {
return;
}
// 指向最小数的索引
int miniIndex;
// 一共要比较n-1次
for (int i = 0; i < a.length -1; i++) {
// 每次都将无序部分第一个数作为最小数，进行比较
miniIndex = i;
// 从最小数的下一个开始比较
for(int j = i+1;j< a.length;j++){
if (a[j] < a[miniIndex]) {
miniIndex = j;
}
}
int temp = a[i];
a[i] = a[miniIndex];
a[miniIndex] = temp;
}
}
}
时间复杂度
由代码分析，第一层循环，一定会执行n-1次，内循环也会执行n-1 ,n -2…….1次，因此 选择排序的时间复杂度是O(n2)。
最好时间复杂度是n
举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
空间复杂度
由于需要一个临时变量记录最小值的下标，所以空间复杂度是O(1)。
