插入排序

今天仍然是O(n^2)级别的排序算法，插入排序。思路也很简单，就是对每一个元素，在其前所有已经排序的元素中，查找一个合适的位置，将该元素放在那个位置上。

实现上，我们将当前元素依次与其前面的元素进行比较，如果前面的元素比当前元素大，则交换这两个元素，直到某个位置，前面的元素比当前元素小，则已完成排序。

template<typename T>
void insertSort(T a[], int n) {
  for(int i = 1; i < n; ++i) {
    for(int j = i; j > 0 && a[j] < a[j-1]; --j) {
      swap(a[j], a[j-1]);
    }
  }
}

与第一课的选择排序相比，该算法存在提前退出的可能性，就是说，如果当前元素已经找到了合适的位置，就不再需要继续与更前面的元素进行比较了。这对于一个基本有序的数组来说，会是一个比较大的性能改进。因此，插入排序在实际应用中也往往非常有用，甚至比其他O(nlgn)的算法的性能表现更好。

但是，上面的实现方法还存在一个问题，就是内层循环中一直在做两个元素之间的交换操作(swap)，而这个操作本身的开销也不低。标准的swap函数的实现如下：

template<typename T>
void swap(T &a, T &b) {
  T temp(a);
  a = b;
  b = temp;
}

可见，swap包含了一个copy构造函数和两个赋值，这往往不能满足我们对性能的需求。因此，我们对插入排序的实现进行优化：

template<typename T>
void insertSort2(T a[], int n) {
  for(int i = 1; i < n; ++i) {
    T tmp = a[i];
    int j;
    for(j = i; j > 0 && a[j-1] > tmp; --j) {
      a[j] = a[j-1];
    }
    a[j] = tmp;
  }
}

我们将swap操作替换成赋值操作以优化swap造成的开销。