最简单的排序算法之一是插入排序（insertion sort）。插入排序由N-1趟排序组成。对于P=1趟到P=N-1趟，插入排序保证从位置0到位置P上的元素为已排序状态。

插入排序利用了这样的事实：位置0到位置P-1上的元素是已排过序的。

下图表达了一般的方法，在第P趟，我们将位置P上的元素向左移动到它在前P+1个元素中的正确位置上。

#include <iostream>
typedef int ElementType; 


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

int main()
{
    int A[] = {34, 8, 64, 51, 32, 21};
    InsertionSort(A, 6);
    for(int i = 0; i < 6; ++i){
        std::cout << A[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

/*test result*/
// 8 21 32 34 51 64 

插入排序的分析

由于嵌套循环的每一次都花费N次迭代，因此插入排序为O(N^2)，而且这个界是精确的，因为以反序输入可以达到该界。

成员存数的数组的一个逆序（inversion）是指数组中具有性质i<j, 但A[i]>A[j]的序偶（A[i], A[j]）。

因此在上面的例子中，输入数据34, 8, 64, 51, 32, 21有9个逆序，即（34,8），（34,32），（34,21），（64,51），（65,32），（64,21），（51,32），（51,21）以及（32,21）。

注意，这正好是需要有插入排序（非直接）执行的交换次数。情况总是这样，因为交换两个不按原序排列的相邻元素恰好消除一个逆序，而一个排过序的数组没有逆序。由于算法中还有O（N）项其他的工作，因此插入排序的运行时间是O（I+N），其中I为原始数组中的逆序数。于是若逆序数是O(N)，则插入排序以线性时间运行。

定理：N个互异数的数组的平均逆序数是N（N-1）/4。通过相邻元素进行排序的任何算法平均需要O（N^2)时间。

一个排序算法通过删除逆序得以向前进行，而为了有效的运行，它必须每次交换删除不止一个逆序。