Java 實作插入排序演算法：原始碼解析與效能特性

演算法核心概念

插入排序模擬整理撲克牌過程：維護已排序區段，逐一將未排序元素插入適當位置。

• 時間複雜度：最佳 O(n)（已有序）、平均/最差 O(n²)
• 空間複雜度：O(1) 原地排序
• 穩定排序：相等元素不交換順序
• 適應性佳：近乎有序數據接近 O(n)

完整實作代碼

package Utils.Sort;

public class InsertSort implements SortStrategy {
    public void sort(Comparable[] obj) {
        if (obj == null) {
            throw new NullPointerException("The argument can not be null!");
        }
        int size = 1;
        while (size < obj.length) {
            insert(obj, size++, obj[size - 1]);
        }
    }

    private void insert(Comparable[] obj, int size, Comparable c) {
        for (int i = 0; i < size; i++) {
            if (c.compareTo(obj[i]) < 0) {
                System.out.println(obj[i]); // 除錯輸出，建議移除
                // 向右平移騰出插入位置
                for (int j = size; j > i; j--) {
                    obj[j] = obj[j - 1];
                }
                obj[i] = c;
                break;
            }
        }
    }
}

邏輯流程圖解

初始：[已排序 | 未排序]
      [  5   |  2, 4, 6, 1, 3  ]

第1輪：插入 2 → [ 2, 5 | 4, 6, 1, 3 ]
第2輪：插入 4 → [ 2, 4, 5 | 6, 1, 3 ]
第3輪：插入 6 → [ 2, 4, 5, 6 | 1, 3 ]  (已在正確位置，無位移)
第4輪：插入 1 → [ 1, 2, 4, 5, 6 | 3 ]
第5輪：插入 3 → [ 1, 2, 3, 4, 5, 6 | ]

代碼優化建議

1. 移除除錯輸出：System.out.println(obj[i]) 影響效能
2. 二分搜尋插入點：將內層線性搜尋 O(n) 優化為 O(log n)（但位移仍為 O(n)）
3. 哨兵優化：陣列索引 0 放最小值，省去邊界檢查
4. 希爾排序：分組插入排序，大幅改善大數據效能

適用場景

• 資料量小（n < 50）
• 資料近乎有序
• 線上排序（串流資料逐筆插入）
• 作為快速排序小分區的基礎排序（切換閾值通常 10-20）

與 Java 內建排序比較

Arrays.sort() 對物件陣列使用 TimSort（合併排序+插入排序混合），對基本型別使用 雙軸快速排序。自行實作主要為教學或特殊約束場景。