回帖：在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素L[0]，它小于L[1..n]中任一记录。所以，我们设元素的类型ElementType中有一个常量-∞，它比可能出现的任何记录都小。如果常量-∞不好事先确定，就必须在决定L是否向前移动之前检查当前位置是否为1，若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时，就将L放入L[0]中，这样也可以保证在适当的时候结束第i遍处理。下面的算法中将对当前位置进行判断。
插入排序算法如下：
procedure Selection_Sort(var L:List);
var
i,j:position;
v:ElementType;
begin
1 for i:=First(L)+1 to Last(L) do
begin
2 v:=L;
3 j:=i;
4 while (jFirst(L))and(L< v) do //循环找到插入点
begin
5 L:=L; //移动元素
6 j:=j-1;
end;
7 L:=v; //插入元素
end;
end;
下面考虑算法Insertion_Sort的复杂性。对于确定的i，内while循环的次数为O(i)，所以整个循环体内执行了∑O(i)=O(∑i)，其中i从2到n。即比较次数为O(n2)。如果输入序列是从大到小排列的，那么内while循环次数为i-1次，所以整个循环体执行了∑(i-1)=n(n-1)/2次。由此可知，最坏情况下，Insertion_Sort要比较Ω(n2)次。

如果元素类型是一个很大的纪录，则算法第5行要消耗大量的时间，因此有必要分析移动元素的次数。经过分析可知，平均情况下第5行要执行n(n-1)/4次，分析方法与冒泡排序的分析相同。
如果移动元素要消耗大量的时间，则可以用链表来实现线性表，这样Insertion_Sort可以改写如下(当然前一个算法同样也适用于链表，只不过没下面这个好，但是下面算法这个比较复杂)：
注意：在下面的算法中链表L增加了一个哨兵单元，其中的元素为-∞，即线性表L的第一个元素�