搜 索

排序算法丨选择排序

  • 343阅读
  • 2021年02月25日
  • 0评论
首页 / 默认分类 / 正文

前言

冒泡排序有一个很显著的缺点:元素两两比较,交换次数太多,所需时间太长。
在现实生活中,冒泡排序也不常用。例如,在体育课/军训,体育老师/教官正指挥学生们按照身高从矮到高的顺序排队,那么你认为老师/教官会使用冒泡排序整理队伍吗?很显然,不会。
需要知道:频繁的数组元素交换意味着更多的内存读写操作,会严重影响代码运行效率。

选择排序(Selection sort),是一种简单直观的排序方法。因其每一轮排序都找到了当前的最小值,这个最小值就是被选中的数字,将其交换至本轮首位。这就是“选择排序”名称的由来。

排序思路

  1. 第一次在待排序序列中找到最小元素,存放到序列的起始位置;
  2. 再从剩余的未排序元素中继续寻找最小元素,然后放到已排序的序列的末尾;
  3. 以此类推,直到所有元素均排序完毕。

也就是说,双重循环遍历数组,每经过一轮比较,找到最小元素的下标,将其交换至首位。

代码实现

public static void Sort1(int[] array) {
  for (int i = 0; i < array.length - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < array.length; j++) {
      // minIndex = array[minIndex] < array[j] ? minIndex : j;
      if (array[minIndex] > array[j]) {
          // 记录最小值的下标
          minIndex = j;
      }
    }
    // 将最小元素交换至首位
    int temp = array[i];
    array[i] = array[minIndex];
    array[minIndex] = temp;
  }
}

异同

与冒泡排序相比,相同点:都是两层循环,时间复杂度都为 O(n^2);都只使用有限个变量,空间复杂度 O(1)
不同点:冒泡排序在比较过程中就不断交换;而选择排序增加了一个变量保存最小值 / 最大值的下标,遍历完成后才交换,减少了交换次数。

所以,选择排序比冒泡排序更具有优势;但这不意味着可以完全取代它。因为还有一个重要的不同点:冒泡排序法是稳定的,而选择排序法是不稳定的。

排序算法的稳定性

什么是排序算法的稳定性?

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[a] = r[b],且 r[a] 在 r[b] 之前,而在排序后的序列中,r[a] 仍在 r[b] 之前,则称这种排序算法是稳定的;否则称为不稳定的。也就是说,当数列包含多个值相等的元素时,经过选择排序后,原有的顺序可能会被打乱。

稳定性的意义

其实它只在一种情况下有意义:当要排序的内容是一个对象的多个属性,且其原本的顺序存在意义时,如果我们需要在二次排序后保持原有排序的意义,就需要使用到稳定性的算法。

例如,如果要对一组商品排序,商品存在两个属性:价格和销量。当我们按照价格从高到低排序后,要再按照销量对其排序,这时,如果要保证销量相同的商品仍保持价格从高到低的顺序,就必须使用稳定性算法。

当然,算法的稳定性与具体的实现有关。在修改比较的条件后,稳定性排序算法可能会变成不稳定的。如冒泡算法中,如果将“左边的数大于右边的数,则交换”这个条件修改为“左边的数大于或等于右边的数,则交换”,冒泡算法就变得不稳定了。

同样地,不稳定排序算法也可以经过修改,达到稳定的效果。最简单的做法:新开一个数组,将每轮找出的最小值依次添加到新数组中,选择排序算法就变成稳定的了。

二元选择排序

选择排序算法也是可以优化的,既然每轮遍历时找出了最小值,何不把最大值也顺便找出来呢?这就是二元选择排序的思想。
使用二元选择排序,每轮选择时记录最小值和最大值,可以把数组需要遍历的范围缩小一倍。

public static void Sort2(int[] array) {
  int minIndex, maxIndex;
  // i 只需要遍历一半
  for (int i = 0; i < array.length / 2; i++) {
      minIndex = i;
      maxIndex = i;
      for (int j = i + 1; j < array.length - i; j++) {
        if (array[minIndex] > array[j]) {
            // 记录最小值的下标
            minIndex = j;
        }
        if (array[maxIndex] < array[j]) {
            // 记录最大值的下标
            maxIndex = j;
        }
      }
      // 如果 minIndex 和 maxIndex 都相等,那么他们必定都等于 i,且后面的所有数字都与 array[i] 相等,此时已经排序完成
      if (minIndex == maxIndex) {
        break;
      }
      // 将最小元素交换至首位
      int temp = array[i];
      array[i] = array[minIndex];
      array[minIndex] = temp;
      // 如果最大值的下标刚好是 i,由于 array[i] 和 array[minIndex] 已经交换了,所以这里要更新 maxIndex 的值。
      if (maxIndex == i) {
        maxIndex = minIndex;
      }
      // 将最大元素交换至末尾
      int lastIndex = array.length - 1 - i;
      temp = array[lastIndex];
      array[lastIndex] = array[maxIndex];
      array[maxIndex] = temp;
  }
}

使用 minIndex 记录最小值的下标,maxIndex 记录最大值的下标。每次遍历后,将最小值交换到首位,最大值交换到末尾,就完成了排序。由于每一轮遍历可以排好两个数字,所以最外层的遍历只需遍历一半即可。
二元选择排序中有一句很重要的代码,它位于 交换最小值交换最大值 的代码中间:

if (maxIndex == i) {
    maxIndex = minIndex;
}

这个判断代码处理了一种特殊情况:如果最大值的下标等于 i,也就是说 arr[i] 就是最大值,由于 arr[i] 是当前遍历轮次的首位,它已经和 arr[minIndex] 交换了,所以最大值的下标需要跟踪到 arr[i] 最新的下标 minIndex。

二元选择排序的效率

在二元选择排序算法中,数组需要遍历的范围缩小了一倍。但无法将选择排序的效率提升一倍——虽然二元选择排序最外层的遍历范围缩小了,但 for 循环内做的事情翻了一倍。
实测会发现二元选择排序的速度确实比选择排序的速度快一点点,它的速度提升主要是因为两点:

  1. 在选择排序的外层 for 循环中,i 需要加到 arr.length - 1,二元选择排序中 i 只需要加到 arr.length / 2
  2. 在选择排序的内层 for 循环中,j 需要加到 arr.length,二元选择排序中 j 只需要加到 arr.length - i

在二元选择排序中,我们可以做一个剪枝优化,当 minIndex == maxIndex 时,说明后续所有的元素都相等,就好比班上最高的学生和最矮的学生一样高,说明整个班上的人身高都相同了。此时已经排序完成,可以提前跳出循环。通过这个剪枝优化,对于相同元素较多的数组,二元选择排序的效率将远远超过选择排序。

和选择排序一样,二元选择排序也是不稳定的。

动画演示

演示动画来自于visualgo

动画演示

复杂度分析

选择排序使用两层循环,时间复杂度为 O(n^2); 只使用有限个变量,并没有用到额外的数据结构,空间复杂度为 O(1)。二元选择排序虽然比选择排序要快,但治标不治本,二元选择排序中做的优化无法改变其时间复杂度,二元选择排序的时间复杂度仍然是 O(n^2);空间复杂度为 O(1)。

参考

LeetCode
程序员小灰
菜鸟教程
打 赏
  • 支付宝
  • 微信
Alipay
WeChatPay
评论区
暂无评论
avatar