七大排序之插入排序

<InsertSort>
算法思路：始终将序列看为Sorted+Unsorted两部分；
初始化：空序列无所谓有序；
迭代：从Unsorted中取出元素e，在有序序列中查找确定位置，有序序列长度增加1；
不变性：随着有序序列规模的递增，其规模为n时，整体有序；
与SelectionSort的比较：左右颠倒、SelectionSort中，无序的前缀部分始终不超过有序部分的最小值，但InsertSort没有这种限制；
性能分析：最好情况O(n) / 最坏情况O(n^2) / 平均性能 O(n^2)
是一种Input-Sensitive算法（Shell排序也是）：算法复杂度不仅取决于问题的规模，更多地取决于输入本身的特性；

void InsertSort(int *a,int lo,int hi)
{
    int n=hi-lo+1;
    for(int j=lo+1;j<lo+n;j++){
        int key=a[j]; //待排序第一个元素
        int i=j-1; //当前已排序的元素的最后一个索引数
        while(i>=lo && key < a[i])
        {
            //数组逐个后移一位，直至找到合适位置将其插入
            a[i+1]=a[i];
            i--;
        }
        a[i+1] = key;//找到合适位置，将key值给i索引后面
    }

}

复杂度分析：
空间复杂度：需要一个记录的辅助空间O(1);
时间复杂度：
最好情况：比较n-1次，无需移动，时间复杂度为O(n)
最坏情况：比较2+3+4+...+n=(n+2)(n-1)/2次，移动次数为∑(i+1)=(n+4)(n-1)/2次(i从2到n);
平均情况：O(n^2)

相关概念<逆序对>