折半插入排序¶

实现代码¶

C
/**
 * 折半插入排序（Binary Insertion Sort）
 * 通过二分查找优化插入位置的确定过程
 * @param A[] 待排序数组，A[0]作为哨兵位使用
 * @param n   数组长度（有效元素个数）
 */
void BinInsert(int A[], int n) {   
    // 从第二个元素开始，逐个插入到已排序序列中
    // 注意：这里i从2开始是因为A[1]是第一个有序元素
    for (int i = 2; i <= n; i++) {
        A[0] = A[i];        // 将待插入元素暂存到A[0]（哨兵位）
        int low = 1;            // 设置查找区间的下界
        int high = i - 1;       // 设置查找区间的上界

        // 使用二分查找确定插入位置
        while (low <= high) {
            int mid = (low + high) / 2;     // 计算中间位置

            // 如果中间元素大于待插入元素，则在左半部分查找
            if (A[mid] > A[0])
                high = mid - 1;
            // 否则在右半部分查找
            else
                low = mid + 1;
        }

        // 将插入位置后的所有元素向后移动一位
        for (int j = i - 1; j >= low; j--)
            A[j + 1] = A[j];

        // 将待插入元素放到正确位置
        A[low] = A[0];
    }
}

算法执行过程图解¶

Text Only

初始数组: [哨兵] [49] [38] [65] [97] [76] [13] [27]
          A[0]  A[1]  A[2]  A[3]  A[4]  A[5]  A[6]  A[7]

第1轮(i=2): 待插入38
查找过程: low=1, high=1
         mid=1, A[1]=49 > 38, high=0
         low > high, 结束, low=1
移动元素: A[1]后移
插入结果: [38] [49] [65] [97] [76] [13] [27]

第2轮(i=3): 待插入65
查找过程: low=1, high=2
         mid=1, A[1]=38 < 65, low=2
         mid=2, A[2]=49 < 65, low=3
         low > high, 结束, low=3
移动元素: 无移动
插入结果: [38] [49] [65] [97] [76] [13] [27]

第3轮(i=4): 待插入97
查找过程: low=1, high=3
         mid=2, A[2]=49 < 97, low=3
         mid=3, A[3]=65 < 97, low=4
         low > high, 结束, low=4
移动元素: 无移动
插入结果: [38] [49] [65] [97] [76] [13] [27]

复杂度分析¶

时间复杂度：O(n²)¶

详细分析：

外层循环：执行 n-1 次（i 从 2 到 n）
二分查找部分：
每次查找时间复杂度为 O(log i)
总计：O(log 2) + O(log 3) + ... + O(log n) = O(n log n)
元素移动部分：
最坏情况下需要移动 i-1 个元素
平均情况下需要移动 (i-1)/2 个元素
总计：O(1 + 2 + ... + n-1) = O(n²)
总体时间复杂度：
虽然查找优化到了 O(n log n)，但移动元素仍需 O(n²)
因此总体时间复杂度为 O(n²)

空间复杂度：O(1)¶

只使用了常数个额外变量（low, high, mid, j）
没有使用额外的存储空间
空间复杂度为 O(1)

关键知识点延伸¶

1. 哨兵的作用¶

C
A[0] = A[i];  // 哨兵位

- 哨兵简化了边界条件的判断 - 避免在移动元素时进行数组越界检查

2. 二分查找优化原理¶

传统插入排序在查找插入位置时采用顺序查找 O(n)，而折半插入排序使用二分查找 O(log n)，虽然整体复杂度未改变，但在实际应用中仍有一定优化效果。

3. 稳定性分析¶

折半插入排序是稳定的排序算法
相等元素的相对位置不会改变

4. 适用场景¶

数据量较小时效率较高
对于部分有序的数组效果更好
适用于链表结构（但无法使用二分查找）

5. 与直接插入排序的比较¶

特性	直接插入排序	折半插入排序
查找时间	O(n)	O(log n)
移动时间	O(n)	O(n)
总时间	O(n²)	O(n²)
空间复杂度	O(1)	O(1)
实现难度	简单	较复杂

算法特点总结¶

优化点：通过二分查找减少了比较次数
局限性：元素移动操作仍需 O(n²) 时间
稳定性：保持了插入排序的稳定性
适用性：适合小规模数据或部分有序数据
改进方向：可结合希尔排序等算法进一步优化