背景

对拥有N个元素的线性表进行排序
假设这N个元素装在数值a中

原理

将新加入的元素先放在末端（或给后面选择的元素），将它在前面排序好的数据中找个合适的位置放置。

时间复杂度

o(n)~o(n*(n-1)/2)

C代码实现

int i,j,k;
for (i=2;i<=n;i++)
{
    j=i; //如果是边读入边插入i的初始值设为1，并且可以在此处添加读入语句
    while ((j-- > 0) && a[j+1]<a[j])
    {
        k=a[j+1];
        a[j+1]=a[j];
        a[j]=k;
    }
}

直接插入排序

int tmp,i,j;
for (i=2;i<=n;i++)
{
    tmp=a[i];
    j=i-1;
    while (j>=0 && tmp<a[j])
    {
        a[j+1]=a[j];
        j--;
    }
    a[j+1]=tmp;
}