1、插入排序2、优化插入排序 - 二分插入排序
1、插入排序什么是插入排序？
重点在插入，每次抽离一个元素当作临时元素，依次比较和移动之后
核心规则：
在第一轮，抽离数组末尾倒数第二个元素，作为临时元素用临时元素与数组后面的元素进行对比：如果后面的元素值小于临时元素，则后面的元素左移如果后面的元素大于临时元素，或者已经移动到数组末尾，则将临时元素插入当前的空袭中重复上面的步骤，完成排序
此处的核心逻辑是通过每次的迭代，将部分元素排好序，经过一定次数的迭代之后，实现最终全部排序的效果
举例：
第一次迭代：
- 首先选中倒数第二个元素 5 作为临时元素将临时元素依次与后面的元素进行对比，5 比 3 大，因此将 3 左移一个此时已经达到了数组的末尾，直接将 5 插入
第二次迭代：
- 首先选中倒数第三个元素 7 作为临时元素依次与后面的元素进行对比，7 比 3 大，将 3 左移一个接下来 7 与 5 比较，7 比 5 大，因此将 5 左移一个已经到达数组的末尾，直接将 7 插入
第三次迭代：
- 首先选中倒数第四个元素 4 作为临时元素依次与后面的元素进行对比，4 比 3 大，将 3 左移一个4 比 5 小，直接将 4 插入当前空隙位置
我们可以发现：每次迭代都可以将末尾部分的元素排好序
时间复杂度：
最好的情况
如果所有的元素都是升序排列，我们每次迭代不需要进行移动元素，所以时间复杂度是 O(N)
最坏的情况
如果所有的元素都是降序排列，我们每次迭代以及迭代中的比较都需要移动，在这种情况下，比较的步数为：O((N^2 + N) / 2)，移动的步数为：O((N^2 + N) / 2)。因此最差的情况为：O(N^2 + N)，忽略常数为：O(N^2)
代码如下：
public static void insertSort(int[] array) {
// 从倒数第二位开始，遍历到底0位，遍历 N-1 次
for (int i = array.length - 2; i >= 0; i--) {
// 存储当前抽离的元素
int temp = array[i];
// 从抽离元素的右侧开始遍历
int j = i + 1;
while (j <= array.length - 1) {
// 如果某个元素，小于临时元素，则这个元素左移一个
if (array[j] < temp) {
array[j - 1] = array[j];
} else {
// 如果大于，则直接将临时元素插入，然后退出循环
array[j - 1] = temp;
break;
}
j++;
}
// 处理到达尾部的情况
if (j == array.length) {
array[j - 1] = temp;
}
}
}
冒泡排序 vs 选择排序 vs 插入排序
冒泡排序和插入排序可以参考橘子的轻松拿下冒泡排序与选择排序这篇文章喔~
2、优化插入排序 - 二分插入排序首先，冒泡排序肯定是比较差的。选择排序和插入排序需要分情况而定
如果原始数组本身有很多元素已经达到理想的排序状态排好序了，那么选择插入排序（比如上面所例举的最好的情况，接近O(N) ）。否则选择选择排序
所以，在实际情况中，还是要根据真实数据的特性来选择相对应的算法
插入算法其最核心的逻辑就是查找应该插入的临时元素的位置，类似于在一个有序数组中查询，找到元素应该插入的位置
如图所示：
图片均选自优课达学习官网
第二次迭代就相当于在第一次迭代结果 [3,5] 中寻找 7 应该插入的位置。第三次迭代就相当于在第二次迭代结果 [3,5,7] 中寻找 4 应该插入的位置
其实对于这种有序列表，循环遍历其实并不是最优解，还有一种更好的方法：二分查找法
因此，将插入排序和二分查找法结合在一起可以进一步提高排序的效率
二分插入法
// 查找应该插入的索引的位置
public static int searchIndex(int[] array, int left, int right, int aim) {
while (left < right) {
int middle = (right + left) / 2;
int value = array[middle];
if (value < aim) {
left = middle + 1;
} else {
right = middle - 1;
}
}
// 如果最终元素仍然大于目标元素，则将索引位置往左边移动一个（判断当前元素和目标元素，看看是否需要插入到当前元素之前）
if (array[left] > aim) {
return left - 1;
}
// 否则就是返回当前的位置
return left;
}
array：原数组
left 和 right：需要插入的区间
aim：需要插入的目标元素
插入排序代码优化
再修改一下插入排序代码，直接利用 searchIndex 查询到的插入位置：
public static void insertSort(int[] array) {
// 从倒数第二位开始，遍历到底0位，遍历 N-1 次
for (int i = array.length - 2; i >= 0; i--) {
// 存储当前抽离的元素
int temp = array[i];
int index = searchIndex(array, i+1, array.length-1, temp);
// 根据插入的索引位置，进行数组的移动和插入。当获取需要插入的位置后，依次移动后面的元素，然后进行插入
int j = i + 1;
while (j <= index) {
array[j - 1] = array[j];
j++;
}
array[j - 1] = temp;
}
}
希望本文能够得到您的认可~~~如果觉得本文有用的话记得来个 点赞 + 关注，或者分享给身边的朋友们，也希望各位大家能够给小橘子一些建议，我们一起加油！
