（PS：内容参考MIT算法导论）

插入排序（Insertion Sort）：

适用于数目较少的元素排序

伪代码（Pseudocode）：

例子（Example）：

符号（notation）：

时间复杂度（Running Time）：

源代码（Source Code）：

#include<iostream>

using namespace std;

template<class T>

void InsertSort(T a[], int n){

for(int j=1;j<n;j++){

T t=a[j];

int i=j-1;

while(i>=0 && a[i]>t){

a[i+1]=a[i];

i=i-1;

}

a[i+1]=t;

}

}

void main(){

int a[]={8,2,4,9,3,6};

InsertSort(a,6);

cout<<"after insertionSort: "<<endl;

for(int i=0;i<6;i++)

cout<<a[i]<<" ";

cout<<endl;

system("pause");

}