## 插入排序 1. 基本思想：在要排序的一组数中，假定前n-1个数已经排好序，现在要将第n个数插到前面的有序数列中，使得这n个数也是有序的。如此反复循环，直到全部拍好顺序。 ``` template <typename T> void insertsort(vector<T>& data) { for (int i = 1; i < data.size(); ++i) { for (int j = i; j > 0 && data[j] < data[j-1]; --j) { swap(data[j], data[j-1]); } } } ``` 2. 优化的插入排序：用赋值而不是交换操作 ``` template <typename T> void better_insertsort(vector<T>& data) { for (int i = 1; i < data.size(); ++i) { T e = data[i]; int j; for (j = i; j > 0 && e < data[j-1]; --j) { data[j] = data[j-1]; } data[j] = e; } } ```