在直接插入排序算法中,是将待排序的元素与已排序序列中的元素进行一一比较,直到找到插入位置,元素的比较次数过多,可通过减少比较次数来优化算法。
算法描述
二分插入排序算法思路与直接插入排序算法一致,只是为了减少待排序元素与已排序元素的比较次数,采用二分查找法来找到待排序元素的插入位置,然后移动元素,将待排序元素插入。
二分插入排序只是减少元素比较次数,并没有减少元素的移动次数,其相对直接插入排序性能并未有本质提升。
代码实现
PHP代码
算法复杂度
时间复杂度:O(n^2)
空间复杂度:O(1)
算法稳定性
二分插入排序仍然是稳定的
可以通过减少比较次数来改进直接插入排序,同样可以通过减少移动次数来改进,下一篇文章将介绍此种改进算法
领取专属 10元无门槛券
私享最新 技术干货