插入排序

1.算法

插入排序由N-1趟排序组成。对于P = 1 趟到 P = N - 1趟，插入排序保证从位置0到位置P上的元素为已排序状态。插入排序利用了这样的事实：位置0到位置 P - 1上的元素是已排过序的。
下表表达了一般的方法。在第P趟，我们将位置P上的元素想做移动到它在前P+1个元素中的正确位置上。下面的程序实现了该想法。第2行到第5行实现数据移动而没有明显使用交换。位置P上的元素存于Tmp，而(在位置P之前)所有更大的元素都被向右移动一个位置。然后Tmp被置于正确的位置上。这种方法与实现二叉堆时所用到的技巧相同。

初始	34 8 64 51 32 21	移动的位置
在p=1之后	8 34 64 51 32 21	1
在p=2之后	8 34 64 51 32 21	0
在p=3之后	8 34 51 64 32 21	1
在p=4之后	8 32 54 51 64 21	3
在p=5之后	8 21 32 34 51 64	4

void InsertionSort(ElementType A[], int N)
{
    int j, P;
    
    ElementType Tmp;
    for( P = 1; P < N; P++)                         //1
    {
        Tmp = A[P];                                 //2
        for( j = P; j > 0 && A[ j-1 ] > Tmp; j--)   //3
            A[j] = A[j-1];                          //4
        A[j] = Tmp;                                 //5
    }
}

2.插入排序的分析

由于嵌套循环的每一个都花费N次迭代，因此插入排序为O(N²)，而且这个界是精确的，因为以反序输入可以达到该界。精确计算指出对于P的每一个值，第4行的测试最多执行P+1次。对所有的P求和，得到总数为
SUM = 2 + 3 + 4 + ... + N = O(N<sup>2</sup>)
另一方面，如果输入数据已排序，那么运行时间为O(N)，因为内层for循环的检测是立即判定不成立而终止。事实上，如果输入几乎被排序，那么插入排序将运行得很快。