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

今天来学习一下选择排序

选择排序的流程如下

给定 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 相等(就没有交换)
  }
}

图示：

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

练习题

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