本篇文章来聊一聊折半插入排序。

基本思想

先来回顾一下直接插入排序的算法思想，就是在前面已经排好序的子序列中寻找一个待插入的位置，然后将待插入元素插入到该位置上。

其中寻找插入位置的过程我们是与每一个元素进行比较，相当于顺序查找，我们知道顺序查找的效率是比较低的，那么有没有办法能够提高查找插入位置的效率呢？

很巧的是，前面的序列既然已经是有序的了，我们何不采用折半查找来找出插入位置呢？折半查找的前提就是序列有序，采用折半查找法查找插入位置的插入排序算法，我们称其为折半插入排序。

图解排序过程

折半插入算法非常简单，前提你得掌握直接插入排序和折半查找的算法，来看一个例子：

原序列的前四个元素已经有序，则从i位置元素开始进行插入排序，先将i位置元素存入下标0作为哨兵，然后在子序列中寻找待插入位置。

这时我们可以采用折半查找法进行查找，定义三个变量low、high和mid，初始low = 1，high = i - 1，则mid为2。

让哨兵位置元素值与mid位置元素值比较，7大于5，所以插入位置应该在右半区࿰

文章来源: blizzawang.blog.csdn.net，作者：·wangweijun，版权归原作者所有，如需转载，请联系作者。

原文链接：blizzawang.blog.csdn.net/article/details/105178831