比较排序算法——插入排序（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(n2)。如果输入序列是从大到小排列的，那么内while循环次数为i-1次，所以整个循环体执行了∑(i-1)=n(n-1)/2次。由此可知，最坏情况下，Insertion_Sort要比较Ω(n2)次。 如果元素类型是一个很大的纪录，则算法第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; 上述改进算法主要是利用链表删除和插入元素方便的特性，对于数组则不适用。 插入排序法是一个原地置换排序法，也是一个稳定排序法。插入法虽然在最坏情况下复杂性为θ(n2)，但是对于小规模输入来说，插入排序法是一个快速的原地置换排序法。许多复杂的排序法，在规模较小的情况下，都使用插入排序法来进行排序，比如快速排序和桶排序。