Java 直接插入排序與折半插入排序算法完整實作

直接插入排序

核心思想

將陣列分為「已排序區」與「未排序區」。初始已排序區僅含首元素，每次從未排序區取首元素，在已排序區中從右向左比較找到插入位置，將較大元素右移，插入該元素。

代碼實作

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 右移
            j--;
        }
        arr[j + 1] = key; // 插入
    }
}

複雜度分析

空間 O(1)，穩定排序。

折半插入排序

優化點

利用已排序區有序特性，採用二分查找定位插入位置，將比較次數從 O(n) 降為 O(log n)。移動次數不變，故時間複雜度仍為 O(n²)，但實際執行較快。

代碼實作

public static void binaryInsertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int low = 0, high = i - 1;
        // 二分查找插入位置 (low 為最終插入點)
        while (low <= high) {
            int mid = (low + high) >>> 1;
            if (key < arr[mid]) high = mid - 1;
            else low = mid + 1;
        }
        // 統一右移：從 i-1 移到 low
        for (int j = i; j > low; j--) arr[j] = arr[j - 1];
        arr[low] = key;
    }
}

兩者對比與應用建議

進階：希爾排序

插入排序的高效改進版，通過分組預排序大幅減少移動次數，平均時間複雜度可達 O(n¹·³) ~ O(n¹·⁵)，是中等規模排序的實用選擇。