Java 經典排序算法：插入排序原理、實現與性能分析

算法思想

插入排序 如同整理撲克牌：將陣列分為「已排序區」與「未排序區」，每次從未排序區取出一張牌，在已排序區中從右向左比較並移位，找到合適位置插入。屬於 原地排序、穩定排序。

代碼實現

public class InsertionSort {

    public static void sort(int[] arr) {
        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--;
            }
            arr[j + 1] = key; // 插入空位
        }
    }

    // 泛型版 (支援 Comparable)
    public static <T extends Comparable<T>> void sort(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;
        }
    }
}

複雜度分析

空間複雜度：O(1) (僅常數額外空間)。

優化變體

1. 二分插入排序

查找插入位置時用 Arrays.binarySearch 或手寫二分，將比較次數降為 O(n log n)，但移動次數仍為 O(n²)，整體仍為 O(n²)，適合「比較昂貴、移動廉價」的對象 (如大對象、字串)。

2. 希爾排序

插入排序的改進版：先按間隔 gap 分組插入排序，逐漸縮小 gap 至 1。時間複雜度視 gap 序列而定 (最佳 O(n log² n))，是唯一突破 O(n²) 的插入類排序。

適用場景

• 資料量小 (n < 50)。
• 資料近乎有序 (如線上系統新增少量資料後重排)。
• 作為快速排序/歸併排序的小區間基準排序 (如 JDK Arrays.sort 對小陣列改用插入排序)。

結語

插入排序雖非大數據首選，但其「簡單、穩定、適應性強」的特性使其成為工程實踐中不可或缺的基石。理解其內循環「比較-移位-插入」機制，有助於掌握更高級的希爾排序與 TimSort (Python/Java 內建排序核心)。