基本思想

它的工作原理是通过构建有序序列，对未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

默认构建个有序数列（就是第一个笑脸吧），设置一个小人作为Criterion，一般设置有序数列的最后一个。

这样后面的小人就不高兴了，我们都是被你默认为无序的。所以后面的小人必须要插队到有序的数列里去。First：我们肯定要从无序的数列中依次把他们插入到有序的数列中去，3号小人首当其冲，向前方已经排序好的数列进军。

具体步骤：

First：我们肯定要从无序的数列中依次把他们插入到有序的数列中去，3号小人首当其冲，向前方已经排序好的数列进军。

Second：一比才发现3号小人他比8号要小，他必须到前面去！这样8号和3号小人就快乐的都有序了。如果发生了后面比前面小那就不用改了！

Third：这时我们要把key改一改了，如果不改的话那不就白给3号和8号排序了。再重复Second

依次类推4号应该插入到3号和6号中间，9号则比有序数列的最后一个数（key）大，不需要再向前扫描换位置了，最终大家快乐的都有序了。

总结一下：直接插入排序就是一个把无序数列依次插入到有序数列中，进行一个在有序数列中的从前向后的扫描，和有序数列进行逐一比较，小就go on 大就go out（不往前走了）。

具体C++代码实现：

**// 插入排序
int main()
{
	int a[200];
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=1; i<n; i++){
		int key = a[i];
		int ii = i-1;
		while (ii>=0 && a[ii]>key)
		{
		a[ii+1] = a[ii];
		ii--;
		}
		a[ii+1] = key;
	}
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
}**