Java 算法入門：插入排序原理圖解與完整實現

算法思想

插入排序的核心思路類似整理撲克牌：將數組分為「已排序區間」和「未排序區間」。初始時已排序區間只有第一個元素。每次從未排序區間取出首個元素，在已排序區間中從右向左比較，找到插入位置，將較大元素右移，騰出空位插入。

動態過程演示

以數組 [7, 5, 3, 4, 2, 1] 為例：

初始: [7 | 5, 3, 4, 2, 1]
i=1: key=5 → [5, 7 | 3, 4, 2, 1]
i=2: key=3 → [3, 5, 7 | 4, 2, 1]
i=3: key=4 → [3, 4, 5, 7 | 2, 1]
i=4: key=2 → [2, 3, 4, 5, 7 | 1]
i=5: key=1 → [1, 2, 3, 4, 5, 7]

完整 Java 實現

public class InsertionSort {
    /**
     * 原地插入排序（升序）
     * @param arr 待排序數組
     */
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        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;          // 插入
        }
    }

    public static void main(String[] args) {
        InsertionSort sorter = new InsertionSort();
        int[] data = {7, 5, 3, 4, 2, 1};
        sorter.sort(data);
        for (int num : data) {
            System.out.println(num);
        }
    }
}

複雜度分析

優化變體

1. 二分查找插入位置（Binary Insertion Sort）

將線性查找改為二分查找，比較次數降為 O(log n)，但移動次數仍為 O(n²)，整體時間複雜度不變，適合比較操作昂貴的場景。

2. 希爾排序

插入排序的改進版，按增量分組插入，時間複雜度可達 O(n^1.3) ~ O(n^1.5)。

適用場景

• 數據量較小（n < 50）
• 數組基本有序（接近最好情況）
• 作為快速排序、歸併排序的小數組基準排序（如 JDK Arrays.sort() 對小數組使用插入排序）
• 在線排序（數據流式到達，需隨時保持有序）

總結

插入排序雖然時間複雜度為 O(n²)，但代碼簡潔、穩定、原地、適應性強，是算法入門必學、工程實戰常用的基礎排序算法。掌握其「查找位置 + 右移元素 + 插入」的核心邏輯，有助於理解更高級的排序算法設計思想。