一、基本思想：

  依次将每个记录（无序表）插入到一个已排好序的有序表中，得到一个新的，记录增加1的有序表；

二、生活实例：

  向扑克牌中插入新牌，图书馆整理图书；

三、过程：

有n个数，将第一个数看做一个有序表，从第二个开始从后向前比较，第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

四、代码实现（C）

void StraightInsertSort（ListR,int n）
{int i,j;
    for{(i=2;i<n;i++)                  //外层循环，标识并据顶待比较的数值；
    {  R[0]=R[i];
        j=i-1;    
        while(R[0].key<R[j].key)   //内存循环，查找循环，与前面的数值依次做比较，确定最终位置
         {
            R[j+1]=R[j];
            j--;
               }
      R[j+1]=R[0];
    }
}

在这里主要想和大家分享一下我对岗哨的理解，所以用了《数据结构导论》中的代码。

五、岗哨：R[0]

我们都能从代码中可以看出它的一个作用：进入查找循环之前，保存要给插入的键值R[i]，使得找到位置后，不至于因为后移其他位置的键值而导致R[i]中的内容；

   另一个作用就是岗哨的作用：在while循环中“监视”数组下标j是否越界，即，待插入的值R[i]向前比较时是否超出数组的范围。j代表数组中的“键”，即每个值的位置，当j=0时，while循环中的判断条件为  while(R[0].key<R[0].key)，此时跳出while循环，将R[0]的查到有序表的最前面；在这里将R[0]设置为岗哨，将判断是否越界（0<=j<=n）和键值之间的比较(R[i]<R[j])融为一体，减少了判断的时间，提高了算法的效率。

六、总结：

稳定；

   空间复杂度O(1)  （需要一个记录的辅助空间）

   时间复杂度O(n2)

   最差情况：反序，需要移动n*(n-1)/2个元素

   最好情况：正序，不需要移动元素

   数组在已排序或者是“近似排序”时，插入排序效率的最好情况运行时间为O(n)，插入排序最坏情况运行时间和平均情况运行时间都为O(n2)。