D&F学数据结构系列——插入排序

插入排序（insertion sort）

插入排序由P-1趟（pass）排序组成。对于P=1趟到P=N-1趟，插入排序保证从位置0到位置P-1上的元素为已排序状态。插入排序利用了这样的事实：位置0到位置P-1上的元素都是已排过序的。

排序过程：如下图，在第P趟，我们将位置P上的元素向左移动到它在前P+1个元素中的正确位置上。位置P上的元素存于tmp，而在P之前的所有更大的元素都被向后移动一个位置。然后tmp被放置于正确的位置上。这种方法在实现二叉堆时所用到的技巧相同。

void InsertionSort(ElementType A[],int N)
{
   int j,P;
   ElementType tmp;
   for(P=1;P<N;P++)
   {
     tmp=A[p];
     for(i=P;j>0&&A[j-1]>tmp;j--)
       A[j]=A[j-1];
     A[j]=tmp;
   }
}