上一节课呢，我们学习了冒泡排序，今天我们就来学学插入排序。
先看一个图
很显然，我们要选出一个数，并找到他的位置，就像图中的一样。
有过一定生活经验的人会发现，这句就是打牌时的理牌嘛！
我们首先要用O(n)的时间来枚举每一个点，再用O(n)的时间查它之前在序列中的应有位置，所以，总复杂度是O(n^2)。
我们来看看代码：
#include<iostream>
using namespace std;
int n,a[10001],t,j,k;//循环之外要用的j,k
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
for(j=i-1;j>=0;j--)
if(a[j]<a[i])//找到比a[i]小的位置就退出，插入其后
break;
if(j!=i-1)
{
t=a[i];
for(k=i-1;k>j;k--)
a[k+1]=a[k];//位置前移一个
a[k+1]=t;
}
}
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}这个代码看似和bubblesort冒泡排序很像，但是它的不同在于使用了全局变量j，k来储存a[i]应有的位置和现在所属的位置。
有时候这个代码很难理解，但是理清思路，最后也是很好理解的。
代码的关键在于：
for(j=i-1;j>=0;j--)
if(a[j]<a[i])
break;
if(j!=i-1)
{
t=a[i];
for(k=i-1;k>j;k--)
a[k+1]=a[k];
a[k+1]=t;
}
其实，说句实话，插入排序的运用真的不广泛。只要懂得，不必太深究。
今天的课程就到这里，明天我们要讲选择排序，我们明天见！
