排序算法入门：选择排序

迷南。 2023-10-06 15:11 15阅读 0赞

**选择排序**

选择排序也是利用了“**挡板法**”这个经典思想。

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

**比如例子：\{5, 2, 0, 1\}**

我们用一个挡板来分隔数组是否排好序，  
用指针 j 来寻找未排序区间的最小值；

![排序算法入门：选择排序][380aefe0ff12a8e36aa9846b7fdd58ff.png]

第一轮 j 最初指向 5，然后遍历整个未排序区间，最终指向 0，那么 0 就和挡板后的第一个元素换一下，也就是和 5 交换一下位置，挡板向右移动一位，结束第一轮。

![排序算法入门：选择排序][0c2cd1dcdb91b1eaa7c17205ca8af0ce.png]

第二轮，j 从挡板后的2开始遍历，最终指向1，然后1和挡板后的第一个元素 2 换一下，挡板向右移动一位，结束第二轮。

![排序算法入门：选择排序][8cea18b7d0897a1794ef9ee25db8cb72.png]

第三轮，j 从2开始遍历，最终指向2，然后和2自己换一下，挡板向右移动一位，结束第三轮。

![排序算法入门：选择排序][ad850257b35b8121d1c22e2967f76c30.png]

还剩一个元素，不用遍历了，就结束了。

选择排序与之前的插入排序对比来看，要注意两点：

1.  挡板必须从 0 开始，而不能从 1 开始。虽然在这两种算法中，挡板的物理意义都是分隔已排序和未排序区间，但是它们的已排序区间里放的元素的意义不同：

*  选择排序是只能把当前的最小值放进来，而不能放其他的；
 *  插入排序的第一个元素可以为任意值。

所以选择排序的挡板左边最开始不能有任何元素。

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 的相对顺序就已经打乱了。

[380aefe0ff12a8e36aa9846b7fdd58ff.png]: https://img-blog.csdnimg.cn/img_convert/380aefe0ff12a8e36aa9846b7fdd58ff.png
[0c2cd1dcdb91b1eaa7c17205ca8af0ce.png]: https://img-blog.csdnimg.cn/img_convert/0c2cd1dcdb91b1eaa7c17205ca8af0ce.png
[8cea18b7d0897a1794ef9ee25db8cb72.png]: https://img-blog.csdnimg.cn/img_convert/8cea18b7d0897a1794ef9ee25db8cb72.png
[ad850257b35b8121d1c22e2967f76c30.png]: https://img-blog.csdnimg.cn/img_convert/ad850257b35b8121d1c22e2967f76c30.png