Java 排序算法總結：插入排序原理與實現

插入排序核心思想

插入排序將數組分為「已排序區」與「未排序區」。初始時已排序區僅含首個元素，每次從未排序區取出首個元素，在已排序區中從後向前掃描，找到插入位置並移動元素騰出空間，完成插入。重複直到未排序區為空。

算法特性

• 時間複雜度：平均/最差 O(n²)，最好 O(n)（已有序）。
• 空間複雜度：O(1)，原地排序。
• 穩定性：穩定，相等元素相對順序不變。
• 適用場景：小規模數據、近乎有序數據、作為快速排序等高級算法的小數組優化閾值。

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

    // 二分查找優化版（僅減少比較次數，移動次數不變）
    public static void binaryInsertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int left = 0, right = i - 1;
            // 二分查找插入位置
            while (left <= right) {
                int mid = (left + right) >>> 1;
                if (arr[mid] > key) right = mid - 1;
                else left = mid + 1;
            }
            // 移動元素
            for (int j = i - 1; j >= left; j--) {
                arr[j + 1] = arr[j];
            }
            arr[left] = key;
        }
    }
}

代碼解析

• 外層循環遍歷未排序區，key 保存待插入值。
• 內層循環從已排序區末尾向前比較，大於 key 的元素右移一位。
• 二分插入排序利用二分查找定位插入點，減少比較次數至 O(n log n)，但元素移動仍為 O(n²)，整體複雜度不變。

優化建議

實際工程中，對於小數組（如長度 < 50），插入排序常比快速排序更快，因無遞歸開銷且緩存友好。Java Arrays.sort() 對小數組即採用雙軸快速排序配合插入排序優化。