二分插入排序 | Baeldung中文网

1. 简介

二分插入排序（Binary Insertion Sort）是插入排序（Insertion Sort）的一种变体。它通过引入二分查找（Binary Search）来优化排序过程，从而提升性能。核心目标是减少比较次数，尤其在比较操作代价较高的场景下效果明显。

2. 插入排序回顾

插入排序的基本思路是：逐步构建一个有序子数组，从数组的第二个元素开始，将当前元素插入到前面已排序子数组中的合适位置，使得整个子数组依然保持有序。

比如：

先判断 x[2] 是否小于 x[1]，如果是就交换；
接着判断 x[3] 应该插入到哪里，使得 x[1] ≤ x[2] ≤ x[3]；
依此类推，直到所有元素都被处理完毕。

插入排序的伪代码如下：

algorithm InsertionSort(x):
    // 输入：数组 x
    // 输出：原地排序后的 x，升序排列

    for i from 2 to n:
        j ← i - 1
        while j > 0 and x[j] > x[j + 1]:
            swap x[j] and x[j - 1]
            j ← j - 1

2.1 插入排序的时间复杂度

最坏情况：输入数组是逆序排列的，此时每轮都要比较和交换 i 次，总操作次数为 (n+2)(n-1)/2，复杂度为 ✅O(n²)。
平均情况：同样是 ✅O(n²)。

3. 二分插入排序原理

二分插入排序的核心思想是：用二分查找确定插入位置，从而减少比较次数。

具体流程如下：

从第 2 个元素开始遍历数组；
对于每个元素 x[i]，在前面已排序的子数组 x[1..i-1] 中使用二分查找，找到其应插入的位置 j；
将 x[i] 插入到 j 的位置，并将 j 到 i-1 的元素整体后移一位。

伪代码如下：

algorithm BinaryInsertionSort(x):
    // 输入：数组 x
    // 输出：升序排序后的数组 x

    for i from 2 to n:
        j ← BinarySearch(x, 1, i - 1, x[i])
        temp ← x[i]
        // 将 j 到 i-1 的元素后移
        for k from i downto j + 1:
            x[k] ← x[k - 1]
        x[j] ← temp

其中 BinarySearch 函数用于查找插入点：

algorithm BinarySearch(a, low, high, target):
    while low <= high:
        mid ← (low + high) / 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            low ← mid + 1
        else:
            high ← mid - 1
    return low

3.1 时间复杂度分析

比较次数：
- 每次插入使用二分查找，比较次数为 log₂(i-1)。
- 总比较次数为 O(n log n)。
移动次数（等价于交换次数）：
- 仍为 O(n²)，因为每次插入仍可能需要移动大量元素。

✅结论：虽然比较次数减少了，但**整体时间复杂度仍为 O(n²)**，与原始插入排序在渐进复杂度上相同。

4. 何时使用二分插入排序？

虽然时间复杂度没有改变，但实际运行效率通常优于普通插入排序，尤其是在以下场景中：

比较操作代价高：例如比较两个对象需要大量计算（如字符串、自定义对象）；
数据量较小：对于小数组或部分有序数组，插入排序本身就很快，加上二分查找后性能更优；
嵌入式系统或性能敏感场景：可以减少 CPU 比较操作，提升整体效率。

❌不推荐使用的情况：

数据量大；
数据完全无序；
交换操作比比较操作更耗时（此时优化比较无意义）。

5. 小结

二分插入排序是对插入排序的优化，通过引入二分查找来减少比较次数，从而在比较代价高的场景下提升性能。

✅主要优点：

比较次数减少至 O(n log n)；
实现简单，适合小数组；
对复杂对象比较场景更友好。

❌主要缺点：

移动操作仍为 O(n²)；
对简单数据类型优化效果不明显；
不适合大规模数据。

📌总结：在特定场景下，二分插入排序是值得使用的优化手段，尤其适合比较操作昂贵但交换操作较快的环境。

Persistence

REST

Security