Java 插入排序算法原理與實現詳解

算法思想

插入排序將數組分為「已排序區」與「未排序區」。初始已排序區僅含首元素。每次從未排序區取出首元素，在已排序區從右向左比較、移位，找到插入位置並放入。類似整理撲克牌。

複雜度分析

Java 完整實現

import java.util.Arrays;

public class InsertionSorting {
    public static void main(String[] args) {
        int[] nums = {4, 3, -1, 9, 2, 1, 8, 0, 6};
        System.out.println("排序前: " + Arrays.toString(nums));

        for (int i = 1; i < nums.length; i++) {
            int key = nums[i];
            int j = i - 1;
            // 從右向左查找插入位置，同時右移元素
            while (j >= 0 && nums[j] > key) {
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = key;
        }

        System.out.println("排序後: " + Arrays.toString(nums));
    }
}

關鍵點解析

• 外層循環從 1 開始：索引 0 默認有序。
• 內層 while 循環：條件 j >= 0 && nums[j] > key 同時保證不越界與找到 ≤ key 的位置。
• 移位而非交換：將大於 key 的元素整體右移一位，最後一次性放入 key，減少賦值次數。
• 適用場景：小規模數組（<50）、近乎有序數組、作為快速排序/歸併排序小分區的基礎排序。

優化變體

• 二分查找插入位置：將內層線性查找優化為 O(log n)，但移位仍為 O(n)，總體仍 O(n²)，適合比較操作昂貴（如對象比較）的場景。
• 希爾排序：插入排序的改進版，按增量分組插入，時間複雜度可達 O(n^1.3) ~ O(n^1.5)。

總結

插入排序代碼極簡、穩定、適應性強（有序時 O(n)），是工程中小數據排序的首選，也是理解高級排序算法的基石。