今天仍然是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造成的开销。
