您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 資料結構與演算法：插入排序 Insertion Sort 完整實作與優化解析

編輯：Java 相關知識

演算法核心思想

插入排序維護一個 已排序區域（左側），每輪從未排序區域取出首個元素（key），向左掃描已排序區域，將大於 key 的元素右移一位，直至找到插入位置。類似整理撲克牌。

標準實作

package al;

public class InsertionSort {
    /**
     * 插入排序（升序）
     * @param array 待排序陣列
     * 時間複雜度：O(n²) 平均/最壞，O(n) 最佳（已排序）
     * 空間複雜度：O(1)
     * 穩定性：穩定（相等元素不交換，僅右移大於 key 的元素）
     * 適應性：強 — 近乎有序資料極快
     */
    public void sort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) { // 從第 2 個元素開始
            int key = array[i];       // 待插入元素
            int j = i - 1;            // 已排序區域最右索引

            // 向左掃描，右移大於 key 的元素
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            // 插入 key 到正確位置
            array[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        InsertionSort sorter = new InsertionSort();
        int[] elements = {14, 77, 21, 9, 10, 50, 43, 14};

        System.out.print("排序前：");
        printArray(elements);

        sorter.sort(elements);

        System.out.print("排序後：");
        printArray(elements);
        // 輸出：9 10 14 14 21 43 50 77
    }

    private static void printArray(int[] arr) {
        for (int v : arr) System.out.print(v + " ");
        System.out.println();
    }
}

執行過程圖解（以 [5, 2, 4, 6, 1, 3] 為例）

初始：[5 | 2, 4, 6, 1, 3]  (| 分隔已排序/未排序)
i=1, key=2：[2, 5 | 4, 6, 1, 3]
i=2, key=4：[2, 4, 5 | 6, 1, 3]
i=3, key=6：[2, 4, 5, 6 | 1, 3]  (6 已在正確位置，無移動)
i=4, key=1：[1, 2, 4, 5, 6 | 3]  (1 移至最左，大量右移)
i=5, key=3：[1, 2, 3, 4, 5, 6]
完成：[1, 2, 3, 4, 5, 6]

複雜度與特性分析

指標	數值	說明
最佳時間複雜度	O(n)	已排序陣列，內層 while 條件即失敗，無移動
平均時間複雜度	O(n²)	約 n²/4 次比較與移動
最壞時間複雜度	O(n²)	逆序陣列，每輪 key 移至最左
空間複雜度	O(1)	原地排序
穩定性	穩定	條件 `array[j] > key`（非 >=），相等不移動
適應性	強	有序度越高越快，部分有序資料表現優異

進階優化：二分查找插入位置（Binary Insertion Sort）

將線性掃描改為二分查找，比較次數從 O(n) 降為 O(log n)，但 移動次數仍為 O(n²)（需右移騰空位置）。

public void binaryInsertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int key = array[i];
        int left = 0, right = i - 1;
        // 二分查找插入位置：第一個 > key 的位置
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (array[mid] > key) right = mid - 1;
            else left = mid + 1;
        }
        // left 即為插入位置，右移 [left, i-1]
        for (int j = i - 1; j >= left; j--) {
            array[j + 1] = array[j];
        }
        array[left] = key;
    }
}

與選擇/冒泡排序對比

維度	插入排序	選擇排序	冒泡排序
最佳情況	O(n)	O(n²)	O(n) (優化版)
穩定性	穩定	不穩定	穩定
寫入/移動次數	O(n²)	O(n) 最少	O(n²)
適應性	強	無	弱 (旗標版)
實務地位	小陣列/近乎有序首選	特定硬體場景	教學為主