折半插入排序：以二分查找優化插入效能

折半插入排序核心改進

折半插入排序是直接插入排序的優化版本。直接插入排序在尋找插入位置時採用線性查找（從右向左逐個比較），時間複雜度為 O(n)；而折半插入排序利用有序區已排序的特性，引入二分查找將尋找插入點的時間複雜度降至 O(log n)，從而減少比較次數（注意：元素移動次數與直接插入排序相同，整體時間複雜度仍為 O(n²)）。

演算法操作流程

1. 外層迴圈遍歷無序區元素（同直接插入排序）。
2. 內層使用二分查找於有序區 [low, high] 確定插入位置：
   • 計算中間索引 mid = (low + high) / 2。
   • 若待插值 < arr[mid]，縮小範圍至 [low, mid-1]；否則縮小至 [mid+1, high]。
   • 迴圈終止條件為 low > high，此時 high + 1 即為插入位置。
3. 將插入位置之後的元素整體後移一位，騰出空間插入待插值。

C 語言完整實現代碼

#include <stdio.h>
#include <stdlib.h>

void InsertSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int temp = arr[i];
        int low = 0, high = i - 1;
        // 二分查找插入位置
        while (low <= high) {
            int mid = (low + high) / 2;
            if (temp < arr[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        // 元素後移
        for (int j = i - 1; j > high; j--)
            arr[j + 1] = arr[j];
        arr[high + 1] = temp;
    }
}

void print(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("排序前：\n"); print(arr, n);
    InsertSort(arr, n);
    printf("排序後：\n"); print(arr, n);
    return 0;
}

效能特性對比

折半插入排序顯著減少了比較操作，適合「比較成本高、移動成本低」的場景（如結構體排序、鏈表轉陣列排序等）。

總結

折半插入排序通過二分查找優化了插入位置的定位，是直接插入排序的經典改進，展示了「查找與排序結合」的演算法設計思想。