每次将一个待排序的元素，按其大小插入到前面已经排好序的子序列中，直到全部元素插入完成为止。

直接插入排序：双重for循环

• 数组长度为n

外循环遍历数组需要n时间，内循环遍历数组需要n时间

最优时间复杂度：数组已有序 O(n)

最差时间复杂度：数组逆序 O(n²)

平均时间复杂度：O(n²)

在原数组上操作，空间复杂度为O(1)

插入排序是稳定的排序算法，重复元素在排序前后的相对位置保持不变

实现方法： for循环 + 二分查找

在直接插入排序中，每一个待排序元素都会依次与有序区内的元素一个一个比较并交换位置，直到找到元素应插入的位置。

折半插入排序则是先利用折半查找算法找到元素应插入的位置，然后进行一次性移动，这样可以减少元素比较的次数，但移动的次数是相同的。