T06. Sorting Algorithms

冒泡排序

冒泡排序就是（假设 ）：

1. 扫一遍 内所有相邻的 和 ，若 则交换。第 大的到达
2. 扫一遍 内所有相邻的 和 ，若 则交换。第 大的到达
3. 扫一遍 内所有相邻的 和 ，若 则交换。第 大的到达
4. 扫一遍 内所有相邻的 和 ，若 则交换。第 大的到达
5. 剩下第 大（最小）的留在

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]);
  }
}

次比较， 次交换。

选择排序

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

1. 扫一遍 ，找到最小的那个，若比 还小则与 交换，此时 是第 小的
2. 扫一遍 ，找到最小的那个，若比 还小则与 交换，此时 是第 小的
3. 扫一遍 ，找到最小的那个，若比 还小则与 交换，此时 是第 小的
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]);
}

次比较， 次交换。

插入排序

没有交换。

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

第 轮结束后，前 个元素是有序的。

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;  // 插入
}

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

总的来说，复杂度 。