插入排序Insertion sort

时间与空间#

n 为元素数，I 为逆序对数量；原地向前移动元素。

时间复杂度

$O(n+I)$；最好 $O(n)$，平均 / 最坏 $O(n^{2})$

辅助空间

$O(1)$

平均二次界以随机排列等常见输入模型为前提；只移动严格大于当前值的元素可保持稳定。二分定位插入位置可减少比较，不能消除数组移动。