侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

选择排序

kaixindeken
2021-04-19 / 0 评论 / 0 点赞 / 64 阅读 / 324 字

实现原理

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

1.png

同样,可以在 VisuAlgo 上看动态图:https://visualgo.net/zh/sorting。

示例代码

void selectionSort(int a[], int N) {
  for (int L = 0; L <= N-2; ++L) { // O(N)
    int X = min_element(a+L, a+N) - a; // O(N)
    swap(a[X], a[L]); // O(1), X may be equal to L (no actual swap)
  }
}

性能分析

  • 很显然,选择排序的时间复杂度也是 O(n2)
  • 由于不涉及额外的存储空间,所以是原地排序;
  • 由于涉及非相邻元素的位置交换,所以是不稳定的排序算法。

综合比较前面介绍的三个排序算法,时间复杂度都是一样的,也都是原地排序,但是选择排序是不稳定的排序算法,此外,插入排序和冒泡排序相比较,我们在将插入排序的时候讲到,插入排序只需要一条语句,而冒泡排序需要三条,在同等条件下,或者数据量很大的情况下,插入排序性能是要优于冒泡排序的,所以综合比较下来,三者的优先级是插入排序 > 冒泡排序 >> 选择排序。

0

评论区