排序演算法詳解：插入排序法

插入排序演算法深度解析

插入排序模擬撲克牌整理手牌的過程：將當前元素插入已排序區域的適當位置，是近乎有序資料的高效選擇。

演算法核心邏輯

1. 從第 2 個元素開始遍歷（視第 1 個為已排序）
2. 取出當前元素，與已排序區域從右向左比較
3. 大於當前元素者向右移動一位
4. 找到插入位置放入當前元素
5. 重複直到所有元素處理完畢

Java 實作程式碼

package com.robert.paixu;

public class InsertSortAlgorithm {
    public static void main(String[] args) {
        int[] arrays = {4, 6, 9, 2, 0, 1, -5, 10, -20, 100, 20, 15};
        insertSort(arrays);
        display(arrays);
    }
    
    private static void insertSort(int[] arrays) {
        for (int i = 1; i < arrays.length; i++) {
            int currentIndex = i;
            int preIndex = i - 1;
            
            while (currentIndex != 0 && preIndex >= 0) {
                if (arrays[currentIndex] < arrays[preIndex]) {
                    swap(arrays, currentIndex, preIndex);
                    currentIndex--;
                } else {
                    break;  // 找到插入位置
                }
                preIndex--;
            }
        }
    }
    
    private static void swap(int[] arrays, int i, int j) {
        int temp = arrays[i];
        arrays[i] = arrays[j];
        arrays[j] = temp;
    }
    
    private static void display(int[] arrays) {
        for (int val : arrays)
            System.out.print(val + " ");
    }
}

執行流程示意

初始: [4, 6, 9, 2, 0, 1, -5, 10, -20, 100, 20, 15]
i=1: [4, 6, 9, 2, ...]     6 > 4，無移動
i=2: [4, 6, 9, 2, ...]     9 > 6，無移動
i=3: [2, 4, 6, 9, ...]     2 插入最前
i=4: [0, 2, 4, 6, 9, ...]  0 插入最前
...
最終: [-20, -5, 0, 1, 2, 4, 6, 9, 10, 15, 20, 100]

複雜度分析

關鍵特性

• 適應性強：資料越有序，比較次數越少，接近 O(n)
• 穩定排序：相等元素相對順序不變
• 線上演算法：可邊讀取資料邊排序，適合串流資料
• 小規模高效：小陣列（n < 50）常快於 O(n log n) 演算法

優化方向

1. 二分搜尋插入位置：將比較次數從 O(n) 降為 O(log n)，但移動次數仍為 O(n²)
2. 希爾排序：插入排序的改良版，透過分組縮減移動距離
3. 雙向插入：同時從左右兩側建立有序區

實務應用場景

• 小規模資料集（如 Arrays.sort() 對小陣列切換插入排序）
• 近乎有序資料（如即時系統增量更新）
• 混合排序算法的基礎組件（TimSort、Introsort）

與選擇排序對比