共计 1528 个字符，预计需要花费 4 分钟才能阅读完成。
抉择排序
抉择排序也是利用了“挡板法”这个经典思维。
挡板右边是已排序区间，左边是未排序区间，那么每次的“抉择”是去找左边未排序区间的最小值，找到之后和挡板前面的第一个值换一下，而后再把挡板往右挪动一位，保障排好序的这些元素在挡板的右边。
比方之前的例子：{5, 2, 0, 1}
咱们用一个挡板来分隔数组是否排好序，
用指针 j 来寻找未排序区间的最小值；
第一轮 j 最后指向 5，而后遍历整个未排序区间，最终指向 0，那么 0 就和挡板后的第一个元素换一下，也就是和 5 替换一下地位，挡板向右挪动一位，完结第一轮。
第二轮，j 从挡板后的 2 开始遍历，最终指向 1，而后 1 和挡板后的第一个元素 2 换一下，挡板向右挪动一位，完结第二轮。
第三轮，j 从 2 开始遍历，最终指向 2，而后和 2 本人换一下，挡板向右挪动一位，完结第三轮。
还剩一个元素，不必遍历了，就完结了。
抉择排序与之前的插入排序比照来看，要留神两点：
- 挡板必须从 0 开始，而不能从 1 开始。尽管在这两种算法中，挡板的物理意义都是分隔已排序和未排序区间，然而它们的已排序区间里放的元素的意义不同：
- 抉择排序是只能把以后的最小值放进来，而不能放其余的；
- 插入排序的第一个元素能够为任意值。
所以抉择排序的挡板右边最开始不能有任何元素。
- 在外层循环时，
- 抉择排序的最初一轮能够省略，因为只剩下最大的那个元素了；
- 插入排序的最初一轮不可省略，因为它的地位还没定呢。
class Solution {public void selectionSort(int[] input) {if(input == null || input.length <= 1) {return;}
for(int i = 0; i < input.length - 1; i++) {
int minValueIndex = i;
for(int j = i + 1; j < input.length; j++) {if(input[j] < input[minValueIndex]) {minValueIndex = j;}
}
swap(input, minValueIndex, i);
}
}
private void swap(int[] input, int x, int y) {int tmp = input[x];
input[x] = input[y];
input[y] = tmp;
}
}
工夫复杂度
最内层的 if 语句每执行一次是 O(1)，那么要执行多少次呢？
- 当 i = 0 时，是 n-1 次；
- 当 i = 1 时，是 n-2 次；
- …
- 最初是 1 次；
所以加起来，总共是：
(n-1) + (n-2) + … + 1 = n*(n-1) / 2 = O(n^2)
是这样算进去的，而不是一拍脑袋说两层循环就是 O(n^2).
空间复杂度
这个很简略，最多的状况是 call swap() 的时候，而后 call stack 上每一层就用了几个无限的变量，所以是 O(1)。
那天然也是原地排序算法了。
稳定性
这个答案是否定的，抉择排序并没有稳定性。
因为替换的过程毁坏了原有的绝对程序，比方: {5, 5, 2, 1, 0} 这个例子，第一次替换是 0 和 第一个 5 替换，于是第一个 5 跑到了数组的最初一位，且再也无翻身之地，所以第一个 5 第二个 5 的绝对程序就曾经打乱了。
这个问题在石头哥的那篇 谷歌面经文章 里有被考到哦，如果还没有看过这篇面经文章的，在公众号里回复「谷歌」二字，就能够看到了。
优化
抉择排序的其中一步是选出每一轮的最小值，那么这一步如果应用 heapify() 来优化，就能够从 O(n) 优化到 O(logn)，这其实就变成了 heapSort.
如果你喜爱这篇文章，记得给我点赞留言哦～你们的反对和认可，就是我创作的最大能源，咱们下篇文章见！
我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！
更多干货文章见我的 Github: https://github.com/xiaoqi6666…