十大排序算法之选择排序
这里不得不先解释一下上一篇文章冒泡排序的空间复杂度，我写的是最好是O(0)这个我可以接受，就是初始数据已经有序。
最坏是O(n), 这个是很多人都在网上说，但是我个人不是很理解为什么是O(n). 因为在for循环里就算我们定义了一个int并且每一次循环都重新赋值，但是按照我的理解，就算循环n次，但是每一次新的循环开始上一次声明的int值就会被回收，这样应该复杂度还是O(1)才对。。。。这里存疑！！！！！！！
所以大家也不要盲目相信网上的文章，毕竟不是官方的。自己稍微验证一下总是好的。共勉！
那么今天来为大家介绍第二种算法，选择排序。这个算法应该是平时排序的时候能用到最多了的吧。。。我反正一般第一时间就是想到这个哈哈。
选择排序（Selection Sort）
应该是最容易被想到的排序方法了，原理如下
在所有未排序的数组中遍历一次找到最小(大)值，然后把找到的值放到数组的最左(右)边。
在剩下无序区域继续执行步骤一的操作
若数组长度为n，则第n-1次会完成完成排序。
动图帧数太大使用不了， 可以直接使用下面的链接进去看一下。很直观易懂
https://upload-images.jianshu.io/upload_images/17400545-e3a784e614fca758.gif?imageMogr2/auto-orient/strip|imageView2/2/w/811/format/webp
不跟你多BB，直接上代码
/*** 每次找到最小值，并记录index， 然后和当前无序区最左边的数进行交换* @param nums 无序数组, nums.length >= 2*/public static void selectionSort(int[] nums) {int left = 0;//为什么是length-1: 因为如果只剩下一个数的时候就不需要比了，因为只剩一个数了while (left < nums.length - 1) {int minValIndex = left;for (int i = left; i < nums.length; i++) {if (nums[i] < nums[minValIndex]) {minValIndex = i;}}int temp = nums[left];nums[left] = nums[minValIndex];nums[minValIndex] = temp;left++;}}
上面是按照算法描述直接进行实现得到的代码，感觉确实是很直观，没什么可解释的了
唯一的一个地方就是循环条件那个地方，我们可以看到最外层我是写的left < nums.length -1，但是里面那层是写的 i < nums.length。
这是因为left是代表左边的有序区已经包含了left个元素，所以当我们的left已经等于倒数第二个元素下标时候，就不需要再进循环了，因为只剩下一个元素了，可以默认放到最后面。
但是内层却不能这么写，因为内层是无序区，你怎么能保证最后一个元素不是这次循环的最小值呢？所以必须是 i < nums.length;
PS：反正无论什么排序算法，写代码的时候把那个下表整明白了你就完成一大半了
但是很多人一定问那我可以最大值和最小值同时排序啊！！
果然天才们的思想都是比较类似，我反正是读这个算法的描述的时候就想的是最大值和最小值一起排。上面那个代码纯粹是为了凑字数哈哈
/*** 每次同时找到最大和最小值，并交换位置到当前无序区的头部和末尾* @param nums 无序数组, nums.length >= 2*/public static void selectionSort1(int[] nums) {int left = 0, right = nums.length - 1;int minValIndex, maxValIndex;while (left < right) {minValIndex = left;maxValIndex = right;//这里一定要注意是<=，因为我们的right=nums.length - 1for (int i = left; i <= right; i++) {if (nums[i] > nums[maxValIndex]) {maxValIndex = i;}if (nums[i] < nums[minValIndex]) {minValIndex = i;}}//交换最小值的位置到最左边int temp = nums[left];nums[left] = nums[minValIndex];nums[minValIndex] = temp;if (left == maxValIndex) {maxValIndex = minValIndex;}//交换最大值的位置到末尾temp = nums[right];nums[right] = nums[maxValIndex];nums[maxValIndex] = temp;left++;right--;}}
这个代码说实话， 我写了一个多小时 我在写完之后自己写了一些测试用例，结果就一直测不过。。肉眼找了将近一个小时才发现问题。
犯了两个错误：
在while里面的那层for循环一定是 i <= right 而不是 i < right
因为我的right取值不是nums.length而是nums.length-1，
心里一万匹草泥马崩腾而过有没有
我每一次都是先交换的最小值，然后再交换最大值。但是如果最大值开始就在最左边的话，一定要将最大值的下标还原。因为当我们交换最小值到最左边的之后，就相当于把最大值换到了minValIndex这个下标的位置，所以这里一定要加下面这段代码。否则你就测吧，哭死你
if (left == maxValIndex) {maxValIndex = minValIndex;}
复杂度和稳定性分析
稳定性：很明显不稳定，就比如[3, 1, 3]，排序完就变成了[1, 3, 3], 红3排序完之后到了绿3的后面。
时间复杂度：这个算法无论是何种情况复杂度都是O(n^2)，所以个人认为数据规模小的时候用用可以，大的话就换别的吧。
空间复杂度：O(1)，没有用到额外的数据结构或内存空间