七大排序之插入排序七大排序之插入排序

【七大排序之插入排序】
算法思路：始终将序列看为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 && 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)
相关概念<逆序对>