Java 基礎排序算法：插入排序原理與代碼實現

算法概念

插入排序的核心思想是將數組分為「已排序區間」與「未排序區間」。初始時，第一個元素視為已排序。每次從未排序區間取出第一個元素，在已排序區間中從後向前掃描，找到合適位置插入，並將後續元素後移。類似整理撲克牌的過程。

算法步驟

1. 假設數組 R[1..n]，初始 R[1] 為有序區，R[2..n] 為無序區。
2. 對 i = 2 到 n：將 R[i] 插入 R[1..i-1] 中，使 R[1..i] 有序。
3. 插入時從 i-1 向前比較，若 R[j] > R[i] 則後移，直到找到 R[j] <= R[i] 或到達開頭。

Java 實現代碼

public static void insertSort(int[] array) {
    int len = array.length;
    for (int i = 1; i < len; i++) {
        for (int j = i; j > 0; j--) {
            if (array[j] < array[j - 1]) {
                // 交換 array[j] 和 array[j-1]
                int temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
            } else {
                break; // 已找到正確位置，提前結束內層循環
            }
        }
    }
}

代碼詳解

• 外層循環：i 從 1 開始，代表當前待插入元素的索引。
• 內層循環：j 從 i 遞減至 1，將 array[j] 與前一元素比較。
• 交換邏輯：若前一元素較大，交換位置（實際為向後移動）。使用 break 優化：一旦發現前一元素不大於當前值，說明前面已有序，無需繼續比較。
• 原地排序：不需要額外陣列空間，空間複雜度 O(1)。

性能特徵

適用場景

• 數據量較小（n < 50）
• 數據基本有序（如已排序數組新增少量元素）
• 作為快速排序、歸併排序的小數組優化閾值（如 Arrays.sort() 中對小數組使用插入排序）
• 在線排序（數據流式到達，需即時維持有序）

圖示演示

（此處原文包含演示圖，建議補充動態圖或 ASCII 圖解）

初始: [5, 2, 4, 6, 1, 3]
i=1: [2, 5, 4, 6, 1, 3]  (2 插入 5 前)
i=2: [2, 4, 5, 6, 1, 3]  (4 插入 5 前)
i=3: [2, 4, 5, 6, 1, 3]  (6 保持)
i=4: [1, 2, 4, 5, 6, 3]  (1 移至開頭)
i=5: [1, 2, 3, 4, 5, 6]  (3 插入 4 前)

進階優化：二分查找插入位置

可將內層線性查找改為二分查找（Binary Insertion Sort），將比較次數從 O(n) 降為 O(log n)，但移動次數仍為 O(n²)，整體複雜度不變，實際性能對小數組提升明顯。

int left = 0, right = i - 1;
while (left <= right) {
    int mid = (left + right) >>> 1;
    if (array[mid] > key) right = mid - 1;
    else left = mid + 1;
}
// left 為插入位置，將 [left, i-1] 整體後移一位