比较排序算法——插入排序（Insertion Sort）

　　插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得 L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个 位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。

图1 对4个元素进行插入排序

　 　在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素L[0]，它小于L[1..n]中任一记录。所以，我们设元素的类型 ElementType中有一个常量-∞，它比可能出现的任何记录都小。如果常量-∞不好事先确定，就必须在决定L[i]是否向前移动之前检查当前位置是 否为1，若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时，就将L[i]放入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[i];
　　3     j:=i;
　　4     while (j<>First(L))and(L[j-1]< v) do  //循环找到插入点
　　        begin
　　5         L[j]:=L[j-1];  //移动元素
　　6         j:=j-1;
　　        end;
　　7     L[j]:=v;  //插入元素
　　    end;
　　end;

　　下面考虑算法Insertion_Sort的复杂性。对于确定的i，内while循环的次数为O(i)，所以整个循环体内执行了∑O(i)=O(∑i)，其中i从2到n。即比较次数为O(n² )。如果输入序列是从大到小排列的，那么内while循环次数为i-1次，所以整个循环体执行了∑(i-1)=n(n-1)/2次。由此可知，最坏情况下，Insertion_Sort要比较Ω(n² )次。

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

　　注意：在下面的算法中链表L增加了一个哨兵单元，其中的元素为-∞，即线性表L的第一个元素是L^.next^

　　procedure Selection_Sort_II(var L:PList);
　　var
　　i,j,tmp:Position;
　　begin
　　1  if L^.next=nil then exit; //如果链表L为空则直接退出
　　2  i:=L^.next;  //i指向L的第一个元素，注意，L有一个哨兵元素，因此L^.next^才是L的第一个元素
　　3  while i^.next<>nil do
　　     begin
　　4      tmp:=i^.next;  //tmp指向L[i]的下一个位置
　　5      j:=L;
　　6      while (j<>i)and(tmp^.data>=j^.next^.data) do //从前向后找到tmp的位置，tmp应该插在j后面
　　7      j:=j^.next;
　　8      if j<>i then  //j=i说明不需要改变tmp的位置
　　         begin    
　　9          i^.next:=tmp^.next;  //将tmp从i后面摘除
　　10         tmp^.next:=j^.next;  //在j后面插入tmp
　　11         j^.next:=tmp;
　　         end
　　12     else i:=i^.next;  //否则i指向下一个元素
　　    end;
　　end;

　　上述改进算法主要是利用链表删除和插入元素方便的特性，对于数组则不适用。

　　插入排序法是一个原地置换排序法，也是一个稳定排序法。插入法虽然在最坏情况下复杂性为θ(n² )，但是对于小规模输入来说，插入排序法是一个快速的原地置换排序法。许多复杂的排序法，在规模较小的情况下，都使用插入排序法来进行排序，比如快速排序和桶排序。