排序算法之：插入排序的优化——二分插入排序（Binary Insertion Sort） 题目描述 给定一个整数数组，你需要使用二分插入排序算法对其进行升序排序。与标准插入排序相比，二分插入排序在寻找插入位置时使用二分查找，从而减少比较次数，但元素移动次数不变。请详细解释该算法的步骤、时间复杂度和适用场景。 解题过程 基本思想 ： 二分插入排序是插入排序的改进版本。在标准插入排序中，当需要将一个新元素插入已排序的子数组时，我们从后往前逐个比较并移动元素。而二分插入排序利用二分查找快速确定新元素的插入位置，减少比较次数，但插入时仍需移动元素。 算法步骤 ： 步骤1 ：从第二个元素开始（索引为1），依次处理每个元素，将其视为待插入元素。 步骤2 ：对当前待插入元素，使用二分查找在已排序的子数组（当前元素之前的数组部分）中寻找合适的插入位置。 初始化左边界 left = 0 ，右边界 right = i-1 （ i 为当前元素索引）。 循环直到 left > right ： 计算中点 mid = (left + right) // 2 。 若待插入元素小于 arr[mid] ，则 right = mid - 1 （插入位置在左侧）； 否则 left = mid + 1 （插入位置在右侧或中点后）。 最终插入位置为 left 。 步骤3 ：将插入位置后的所有元素向右移动一位，腾出空间。 步骤4 ：将待插入元素放入位置 left 。 重复直到所有元素处理完毕。 示例演示 （数组 [5, 2, 4, 6, 1] ）： i=1 ：待插入元素 2 ，已排序子数组 [5] 。二分查找：比较 2 < 5 ，插入位置为0。移动元素后数组为 [2, 5, 4, 6, 1] 。 i=2 ：待插入 4 ，子数组 [2, 5] 。二分查找：先比中点 2 （索引0）， 4 > 2 → 右移；再比 5 （索引1）， 4 < 5 → 插入位置1。移动后为 [2, 4, 5, 6, 1] 。 i=3 ：待插入 6 ，子数组 [2, 4, 5] 。二分查找后插入末尾，无需移动。 i=4 ：待插入 1 ，子数组 [2, 4, 5, 6] 。二分查找后插入位置0，移动元素得最终结果 [1, 2, 4, 5, 6] 。 复杂度分析 ： 时间复杂度 ： 二分查找每次比较次数为 O(log n)，共 n-1 次插入，比较总次数为 O(n log n)。 但元素移动仍需 O(n²)（最坏情况下每次插入移动近 n 个元素）。 因此整体时间复杂度仍为 O(n²) ，但优于标准插入排序的 O(n²) 比较次数。 空间复杂度 ：O(1)（原地排序）。 适用场景 ： 适用于小规模或部分有序数组，且 比较成本远高于移动成本 的场景（如字符串排序）。 若移动成本高（如链表），则标准插入排序更合适（因链表移动开销小）。 与标准插入排序对比 ： 优势：减少比较次数，在比较操作昂贵时效率提升明显。 劣势：代码稍复杂，且无法优化移动次数。