常见排序算法4——二分插入排序

在直接插入排序算法中，是将待排序的元素与已排序序列中的元素进行一一比较，直到找到插入位置，元素的比较次数过多，可通过减少比较次数来优化算法。

算法描述

二分插入排序算法思路与直接插入排序算法一致，只是为了减少待排序元素与已排序元素的比较次数，采用二分查找法来找到待排序元素的插入位置，然后移动元素，将待排序元素插入。

二分插入排序只是减少元素比较次数，并没有减少元素的移动次数，其相对直接插入排序性能并未有本质提升。

代码实现

PHP代码

算法复杂度

时间复杂度：O(n^2)

空间复杂度：O(1)

算法稳定性

二分插入排序仍然是稳定的

可以通过减少比较次数来改进直接插入排序，同样可以通过减少移动次数来改进，下一篇文章将介绍此种改进算法