Java 實現折半插入排序：二分查找優化插入位置

折半插入排序：用二分查找將插入定位從 O(n) 降為 O(log n)

針對直接插入排序「查找插入位置」的線性掃描瓶頸，引入二分查找優化。注意：數據後移仍需 O(n)，整體時間複雜度仍為 O(n²)，但比較次數顯著減少。

算法邏輯

1. 外層遍歷無序區 [1, n-1]
2. 有序區 [0, i-1] 內二分查找插入位置 high+1
3. 將 [high+1, i-1] 區間整體後移一位
4. 插入當前元素

完整代碼

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

關鍵點解析

• low + (high - low) / 2 防止溢出
• 循環結束時 high 指向最後 ≤ temp 的元素，插入位置為 high + 1
• 後移循環 j > high 精確覆蓋需移動區間

效能對比

對於比較操作昂貴（如複雜對象、自定義 Comparator）的場景，折半插入排序優勢明顯。