选择排序

核心思想

选择排序 ，也是将数组分成两部分，前面部分是有序的，后面部分每趟排序，从i到N-1的部分中 选择出一个最小的元素，然后交换到前面部分的后面。 第一趟排序比较长度是N，因为从N个元素中找出最小的，第二次就是N-1了，….依次递减比较的长度。 所以经过了这几趟排序就可以把数组排序好。 我们选择排序其实就是选择无序中的最小，然后与有序序列的后一个元素交换！

思考步骤

1.首先要有一个比较基准也就是，INFINITY作为初始化，保证数组中的所有元素都比这个数小。 2. 然后我们最外层是0到N-1趟排序，我们趟都是从无序部分找出一个最小的元素。 3. 每一趟排序完，注意都是要把MIN和MinPos设置回初始值，即INFINITY和-1 4. 比较的时候就是不断更新min和MinPos的值。 5. 每一趟最后就是交换A[i]和A[min]

算法实现

public static final int INFINITY=99999; public void SelectionSort(int[] A){ if(A==null||A.length<1) return; int len=A.length; for(int i=0;i<len;i++){ int MIN=INFINITY int MinPos=-1; for(int k=i;k<len;k++){ if(A[k]<MIN){ MIN=A[k]; MinPos=k; } } //交换注意，一定是交换A[MinPos],MIN只是个判断基准数 int tmp=A[i]; A[i]=A[MinPos]; A[MinPos]=A[i]. } }

性能分析

时间复杂度 最好情况： 即便是有序的，还是会比较N个找最小的元素！ 最坏情况：O(N^2) 平均： O(N^2)

空间复杂度 O(1) 并没有额外使用数组或其他数据结构。

稳定性 显然是一个不稳定的算法。 因为选择出最小的元素直接与前面有序的后一个元素交换。 比如一个序列 {1，2,7，5，3，5} –>{1,2,3,5,7,5} , 此时i所在的数是 左边的第一个5，右边的5是无序部分的， 而无序部分显然找出来的最小元素是5， 那么尽管这两个数是相等的，它们还是要交换！ 因为左边的第一个5是有序的后一个元素，而右边的5是无序中的最小元素！