插入排序的思想是假设前n个元素是有序的，那么就把第n+1个元素插入到前n个元素中的适当位置，直到第m个元素
假设我有个数组{3,1,4,2}
那么对于第一次遍历来说：
有序的就是 arr[0] 要插入的是arr[1]
经过比较后 第一轮的结果变为 {1,3,4,2}
对于第二次遍历：
现在有序的是{1,3} 要插入的是 arr[2]
经过比较后 变为 {1,3,4,2}
对于第三次遍历:
现在有序的是{1,3,4} 要插入的是 arr[3]
经过比较 变为 {1,2,3,4}
排序结束

插入排序的平均时间复杂度为O(n * n)，空间复杂度为O(1),最好情况下时间复杂度为O(n)，最坏情况下为O(n * n)

排序工具类的书写可以参考 我的另一篇文章
链接: 排序算法：冒泡排序

如果数组本身基本有序 下列代码片段基本不会进入

所以时间复杂度就应该该是外层for循环，循环的次数，所以最好情况下时间复杂度为O(n)