关于java:排序算法入门之选择排序

抉择排序也是利用了“挡板法”这个经典思维。

挡板右边是已排序区间，左边是未排序区间，那么每次的“抉择”是去找左边未排序区间的最小值，找到之后和挡板前面的第一个值换一下，而后再把挡板往右挪动一位，保障排好序的这些元素在挡板的右边。

比方之前的例子：{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…

关于java:排序算法入门之选择排序

抉择排序

工夫复杂度

空间复杂度

稳定性

优化