插入排序（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=;P<N;P++)

    {

      tmp=A[p];

      for(i=P;j>&&A[j-]>tmp;j--)

        A[j]=A[j-];

      A[j]=tmp;

    }

 }