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

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

困而学,学而知

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

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

排序算法的时间复杂度

选择排序

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

话不多说,我们先来从数组: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) 的排序算法。(归并排序和快速排序)

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://baozi.fun/2019/12/24/choose-sort

Buy me a cup of coffee ☕.