排序（一）：简单排序

插入排序：你理扑克牌的方式

插入排序正是大多数人理一手牌的方式。让数组的左半部分保持有序；取下一个元素，把它向左滑过所有比它大的，直到落入正确位置。每走一步，有序区就增长一个。

Sorting [ 5  2  4  1 ] by insertion (| marks end of sorted region):

  [ 5 | 2  4  1 ]   take 2, slide past 5     -> [ 2  5 | 4  1 ]
  [ 2  5 | 4  1 ]   take 4, slide past 5     -> [ 2  4  5 | 1 ]
  [ 2  4  5 | 1 ]   take 1, slide to front   -> [ 1  2  4  5 | ]
  done.

每一趟把一个元素插入到已经有序的左侧区域。

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { // slide larger ones right
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;               // drop key into the gap
    }
}

在近乎有序的输入上，内层循环几乎不动——接近 O(n)。

选择与冒泡，略说

选择排序反复扫描未排序部分，找出最小元素并把它交换到前面。冒泡排序反复走过数组，交换相邻的逆序对，于是大的值"冒"到末尾。三者都是简单的嵌套循环。

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int m = i;                       // index of smallest in a[i..]
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[m]) m = j;
        std::swap(a[i], a[m]);           // put it at position i
    }
}

选择排序：找最小，换到前面，重复。

选择排序有一点做得好：它总共最多做 n−1 次交换——比其他两种都少。如果交换远比比较昂贵（大型记录），这一点其实有用。冒泡排序在实践中是三者里最慢的，多半只作为教学例子保留，并不用于真实场景。

为何三者都是 O(n^2)

每一种在最坏情况下大约做 n 趟，每趟触碰至多 n 个元素——嵌套循环，所以是 O(n^2) 次比较。输入翻倍，工作量大约翻四倍。这对几十的 n 没问题，对百万的 n 就很痛苦。

插入排序有个可爱的最好情况：在已经有序（或近乎有序）的数据上，内层 `while` 从不挪动任何东西，于是它以 O(n) 运行。选择排序则不论输入如何，总是做同样的 n^2/2 次比较。

那为何还要教它们？

它们容易写对——比快速排序更少藏 bug 的地方。
插入排序对小数组和近乎有序的数据是真正的最佳选择——真实的库会在子数组很小时切换到它。
它们的循环不变式和逐趟行为，培养出归并排序与快速排序将要倚靠的直觉。

下一篇我们用归并排序和快速排序突破 O(n^2) 的天花板——两者都直接建立在上一篇的分治思想之上。