插入排序

原理  

　      从形象开始，先看下面这一张图。

　　　　图 1：扑克牌理牌¹
   这是大家玩扑克牌的摸牌阶段，我们使用左手拿着已经摸到并排好大小的牌，右手从牌堆里边摸牌，每摸一张牌就将其插入到左手理顺的牌中，插入后保持其大小顺序。
   再把这个过程抽象化，我们的扑克牌就是输入的待排序序列，两只手看成序列的两个部分。已经排序的和未排序的两部分，每次不断的从未排序的部分中取一个数，到已经排序的  部分中找到合适的位置插入。通常是自右向左依次比较来确定。

实现  

        我们使用数组实现上面的过程。初始状态下，数组的首元素为已排序部分，从第二个元素开始插入排序。C语言的实现：
 

 void insertSort(int A[],int len)
   {
       int i,p,k;
       for(i=1;i<len;i++)
       {
           k = A[i];
           p = i-1;
           while(A[p]>k)
           {
               A[p+1] = A[p];
               p--;
           }
           A[p+1]=k;
       }
   }

性能评估 

        在最糟糕的情况下，也就是序列逆序排列时，对于n-1个数中第x个数，每次将该数插入时将引起x-1次数组移动（这里不计算比较时间）,求和得到 n(n-1)/2，很明显时间复杂度为O(n²)。

---

1. 此图出自算法导论2.1中插入排序插图。