排序篇之选择排序-从零开始学习算法

释放双眼,带上耳机,听听看~!

今天来学习一下选择排序

选择排序的流程如下

给定 N 个元素和 L = 0 的数组(初始指针为0),选择排序将:

  1. 在 [L ... N-1] 范围内找出最小元素 X 的位置,
  2. 用第 L 项交换X,
  3. 将下限 L 增加1并重复步骤1直到 L = N-2。

在不失普遍性的情况下,我们也可以实现反向的选择排序:找到最大元素 Y 的位置并将其与最后一个元素交换。

实现代码如下:

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 可能和 L 相等(就没有交换)
  }
}

图示:

QQ20190329-125745-HD.gif

选择排序的复杂度: O(N2) — 其实选择排序和冒泡排序很像。

练习题

数组[29, 10, 14, 37, 13] 在选择排序中实际上需要完成()次交换操作?
3
2
4
1

人已赞赏
从零开始学算法

排序篇之冒泡排序-从零开始学习算法

2019-3-29 13:02:14

未分类

Blender插件-三维模型绘制工具 QuickShape v1.3

2021-1-13 13:34:32

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索