跳转至

T06. Sorting Algorithms

冒泡排序

冒泡排序就是（假设 $n=5$）：

  1. 扫一遍 $[0,4]$ 内所有相邻的 $a_i$ 和 $a_{i+1}$，若 $a_i > a_{i+1}$ 则交换。第 $1$ 大的到达 $a_4$
  2. 扫一遍 $[0,3]$ 内所有相邻的 $a_i$ 和 $a_{i+1}$，若 $a_i > a_{i+1}$ 则交换。第 $2$ 大的到达 $a_3$
  3. 扫一遍 $[0,2]$ 内所有相邻的 $a_i$ 和 $a_{i+1}$，若 $a_i > a_{i+1}$ 则交换。第 $3$ 大的到达 $a_2$
  4. 扫一遍 $[0,1]$ 内所有相邻的 $a_i$ 和 $a_{i+1}$，若 $a_i > a_{i+1}$ 则交换。第 $4$ 大的到达 $a_1$
  5. 剩下第 $5$ 大（最小）的留在 $a_0$
for (int rightmost = n - 1; rightmost > 0; --rightmost) {
  for (int i = 0; i + 1 <= rightmost; ++i) {
    if (a[i] > a[i + 1]) swap(a[i], a[i + 1]);
  }
}

$O(n^2)$ 次比较，$O(n^2)$ 次交换。

选择排序

思路是，进行 $n$ 轮循环。第 $i$ 轮循环确定第 $i$ 小的值。依然假设 $n=5$：

  1. 扫一遍 $[1,4]$，找到最小的那个，若比 $a[0]$ 还小则与 $a[0]$ 交换，此时 $a[0]$ 是第 $1$ 小的
  2. 扫一遍 $[2,4]$，找到最小的那个，若比 $a[1]$ 还小则与 $a[1]$ 交换，此时 $a[1]$ 是第 $2$ 小的
  3. 扫一遍 $[3,4]$，找到最小的那个，若比 $a[2]$ 还小则与 $a[2]$ 交换，此时 $a[2]$ 是第 $3$ 小的
  4. 扫一遍 $[4,4]$，找到最小的那个，若比 $a[3]$ 还小则与 $a[3]$ 交换，此时 $a[3]$ 是第 $4$ 小的
  5. 最后剩下的 $a[4]$ 就是最大的那个（第 $5$ 小）
for (int now = 0; now < n; ++now) {
  int minPos = now;
  for (int i = now; i < n; ++i) {
    if (a[i] < a[minPos]) minPos = i;
  }
  swap(a[now], a[minPos]);
}

$O(n^2)$ 次比较，$O(n)$ 次交换。

插入排序

没有交换。

想象理扑克牌的过程。一开始手里有一张。然后抹一张牌，找到合适的位置，把该放在后面的牌挪开，然后把新抹的这张牌插进去。

第 $i$ 轮结束后，前 $i+1$ 个元素是有序的。

for (int nextPos = 1; nextPos < n; ++nextPos) {
  int val = a[nextPos];
  int pos = nextPos - 1;
  while (pos >= 0 && a[pos] >= val) {
    a[pos + 1] = a[pos];  // 后移
    pos -= 1;
  }
  a[pos + 1] = val;  // 插入
}

对于已经有序的数组，复杂度是 $O(n)$ 的。对于逆序的数组，跟冒泡排序没啥差别。

总的来说，复杂度 $O(n^2)$。