模块1：线性扫描，试图将每个a[i]插入到前面的有序序列中。

模块2：[0, i]的无序区间进行扫描，找出插入的位置，该位置使得插入的瞬间：[0, k]区间有序，而[k+1, i]区间无序，所以插入点在k+1。

#include 
     
      #include 
      
       using namespace std;template 
       
        void insertionSort(vector
        
         & a);int main(){    vector
         
           a;    a.push_back(2);    a.push_back(3);    a.push_back(1);    insertionSort(a);    for (auto x : a)        cout << x << endl;    return 0;}template 
          
            void insertionSort(vector
           
            & a){ for(int i = 1; i < a.size(); i++){ T key = a[i]; int j = i - 1; while( j >= 0 && key < a[j]){ a[j+1] = a[j]; j--; } a[j+1] = key; }}