不稳定的原地排序算法：选择排序

在之前的文章中，我们说了两个原地排序算法：插入排序和冒泡排序。分析两个算法的原理，也用代码实现了两个算法。最后，我们也从两个算法入手，引出了评价算法性能的两个重要指标：是否是原地排序算法和算法稳定性。今天我们再来说一种原地排序算法：** 选择排序**。

为了，我们能够更好地与之前文章中的两个算法作比较，我们还是还是将上一篇文章关于排序算法复杂度的图片祭出。

排序算法的时间复杂度

选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

话不多说，我们先来从数组：4，6，5，2，1，3，来看选择排序的原理分析图。

选择排序原理示意图

可以看到，上图的原理分析和我们在文章开始描述的一样，分为已排序和未排序区间。且每次都是从未排序区间中选出最小的数值放到已排序区间的末尾。

选择排序代码实现

public static void chooseSort(int[] arr) {
  System.out.println(Arrays.toString(arr));
  for (int i = 0; i < arr.length - 1; i++) {
    int min = arr[i];
    int minIndex = i;
    for (int j = i + 1; j < arr.length; j++) {
      // 找出未排序区间中最小的值
      if (arr[j] < min) {
        min = arr[j];
        minIndex = j;
      }
    }
    // 放到已排序区间的末尾
    if (min != arr[i]) {
      arr[minIndex] = arr[i];
      arr[i] = min;
    }
    System.out.println(Arrays.toString(arr));
  }
}

我们来看看输出：

选择排序输出

即使在最好的情况下，选择排序也会有一个嵌套循环，也就是选择排序的最好时间复杂度为O(n2)，幸运的是，选择排序的最坏时间复杂度也是O(n2)。

排序算法分析

和插入排序与冒泡排序算法文章类似，在文章末尾，我们还是照常来分析分析选择排序算法。

是否是原地排序算法

先来回顾一下，什么原地排序算法。原地排序算法是指：数组排序前后，不占用额外内存空间。

答案显而易见，选择排序排序前后只有位置的交换，并没有占用额外存储空间，所以选择排序算法是原地排序算法。

是否是稳定算法

同样的，回顾一下，什么是稳定算法。稳定算法是指：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

选择排序是一种不稳定的排序算法。我们可以从上面的图片中看出，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

比如说：5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。

简单总结一下，本文讲了一个不稳定的原地排序算法：选择排序。从示意图一步一步的分析选择排序，引出选择排序算法算法复杂度。

文章末尾

选择排序、插入排序和冒泡排除这三种排序算法，实现代码都非常简单，对于小规模数据的排序，用起来非常高效。但是在大规模数据排序的时候，这个时间复杂度还是稍微有点高，所以我们更倾向于时间复杂度为 O(nlogn) 的排序算法。（归并排序和快速排序）