Java 插入排序完整實現：直接插入與折半插入兩種變體

插入排序核心思想

插入排序將陣列分為已排序區與未排序區，每次從未排序區取出首元素，在已排序區中由後向前掃描找到插入位置，並將較大元素右移騰出空位。時間複雜度 O(n²)，空間 O(1)，穩定排序，適合小規模或近乎有序資料。

Java 版完整實現

1. 直接插入排序

public class InsertionSort {

    /**
     * 直接插入排序 - 升序
     * @param arr 待排序陣列 (原地修改)
     */
    public static void directInsertionSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];           // 當前待插入元素
            int j = i - 1;

            // 從右向左掃描已排序區，將大於 key 的元素右移
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 插入位置為 j+1
            arr[j + 1] = key;
        }
    }

    // 測試
    public static void main(String[] args) {
        int[] data = {5, 2, 9, 1, 5, 6};
        directInsertionSort(data);
        System.out.println(Arrays.toString(data)); // [1, 2, 5, 5, 6, 9]
    }
}

2. 折半插入排序 (Binary Insertion Sort)

優化查找插入位置：使用二分搜尋將比較次數從 O(n) 降為 O(log n)，但移動次數不變，整體仍為 O(n²)。

public static void binaryInsertionSort(int[] arr) {
    if (arr == null || arr.length <= 1) return;

    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int left = 0, right = i - 1;

        // 二分搜尋插入位置：找到第一個大於 key 的位置
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // left 即為插入位置

        // 統一右移：從 i-1 移到 left
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
}

兩種變體詳細對比

關鍵細節與避坑指南

邊界條件處理

• 外層迴圈從 i = 1 開始（單元素視為已排序）
• 內層條件 j >= 0 防止索引越界
• 折半插入的 left <= right 含等號，確保找到最左插入位

泛型化支援 Comparable

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

實戰優化：混合排序策略

Java Arrays.sort() 對小陣列（< 47-50 元素）正是使用插入排序：

// 簡化版 TimSort 思想
public static void hybridSort(int[] arr) {
    if (arr.length < 50) {
        insertionSort(arr);
    } else {
        // 快排/歸併排序
        Arrays.sort(arr); // 或自行實現
    }
}

效能實測參考 (10 萬隨機整數)

• 直接插入：~12 秒
• 折半插入：~10 秒 (比較減少但移動主導)
• Arrays.sort (雙軸快排)：~0.02 秒

結論：教學理解用插入排序，生產環境大數據必用 O(n log n) 演算法。