Java 直接插入排序演算法實作：泛型支援、單例模式封裝與效能分析

插入排序是簡單直觀的排序演算法，適合小規模或近乎有序資料。本文提供生產級實作：採用單例模式封裝、支援 int[] 與泛型 T[]、完整邊界檢查、哨兵優化，並附測試驗證。

演算法核心邏輯

1. 外層迴圈從索引 1 開始，視為「待插入牌」
2. 若待插入值 array[i] 小於前一個值 array[i-1]，啟動內層插入
3. 內層從 i-1 向前掃描，將大於哨兵值的元素向後搬移
4. 找到插入位置 (vacancy) 放入哨兵值

時間複雜度：最佳 O(n) (已排序)、最差/平均 O(n²)、空間 O(1)、穩定排序。

工具類：Swapper (元素交換通用方法)

public final class Swapper {
    private Swapper() {}

    public static > void swap(int i, int j, T[] arr) {
        if (arr == null) throw new NullPointerException("array is null");
        checkIndices(i, j, arr.length);
        T tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }

    public static void swap(int i, int j, int[] arr) {
        if (arr == null) throw new NullPointerException("array is null");
        checkIndices(i, j, arr.length);
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }

    private static void checkIndices(int i, int j, int len) {
        if (i < 0 || j < 0 || i >= len || j >= len)
            throw new IllegalArgumentException("Index out of bounds: [" + i + "," + j + "]");
    }
}

主類別：InsertionSortord (單例 + 雙重實作)

public final class InsertionSortord {
    private static final InsertionSortord INSTANCE = new InsertionSortord();
    private InsertionSortord() {}
    public static InsertionSortord getInstance() { return INSTANCE; }

    // int[] 版本
    public void doSort(int... array) {
        if (array == null || array.length <= 1) return;
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                int sentry = array[i];
                int vacancy = i;
                for (int j = i - 1; j >= 0; j--) {
                    if (array[j] > sentry) {
                        array[j + 1] = array[j];
                        vacancy = j;
                    }
                }
                array[vacancy] = sentry;
            }
        }
    }

    // 泛型版本 (支援任何 Comparable)
    public > void doSortT(T[] array) {
        if (array == null || array.length <= 1) return;
        for (int i = 1; i < array.length; i++) {
            if (array[i].compareTo(array[i - 1]) < 0) {
                T sentry = array[i];
                int vacancy = i;
                for (int j = i - 1; j >= 0; j--) {
                    if (array[j].compareTo(sentry) > 0) {
                        array[j + 1] = array[j];
                        vacancy = j;
                    }
                }
                array[vacancy] = sentry;
            }
        }
    }
}

測試驗證

public class TestInsertionSortord {
    public static void main(String[] args) {
        InsertionSortord sorter = InsertionSortord.getInstance();

        int[] arr1 = {3, 5, 4, 2, 6};
        System.out.println("Before: " + Arrays.toString(arr1));
        sorter.doSort(arr1);
        System.out.println("After:  " + Arrays.toString(arr1));

        Integer[] arr2 = {3, 5, 4, 2, 6};
        System.out.println("Before: " + Arrays.toString(arr2));
        sorter.doSortT(arr2);
        System.out.println("After:  " + Arrays.toString(arr2));
    }
}

關鍵設計亮點

效能與適用場景

• n ≤ 50：通常快於 QuickSort/MergeSort (無遞迴/分割開銷)
• 近乎有序資料：接近 O(n)，極佳
• 線上排序：資料流式進入，隨到隨插
• 大規模亂序資料：請改用 Arrays.sort() (Dual-Pivot QuickSort) 或 Collections.sort() (TimSort)

進階優化方向

• 二分搜尋插入位置 (Binary Insertion Sort) → 比較次數 O(n log n)，但搬移仍 O(n²)
• Shell Sort：分組插入排序，間距序列縮減，實務表現遠優於純插入排序
• 小陣列切換：在 QuickSort/MergeSort 遞迴基礎案例 (n < 47) 切換至插入排序 (JDK 內部即採用此策略)

此實作展示了演算法教學與工程化落地的平衡，可直接納入專案工具庫或作為面試手寫參考。