折半插入排序
折半插入排序（Binary Insertion Sort）是对直接插入排序的改进。
基本思想
基于直接插入排序，利用二分法优化查找插入位置的部分，降低比较带来的复杂度。
与直接插入排序的区别
只修改了比较部分（使用折半查找确定插入位置），移动部分保持不变。
算法分析
- 比较次数减少到 O(n log n)
- 移动次数不变，仍为 O(n²)
- 总体时间复杂度仍为 O(n²)
- 空间复杂度：O(1)
- 稳定性：稳定
链接到
- 上一个知识点：6.2 直接插入排序
- 下一个知识点：6.4 希尔排序