演算法原理：

  1. 將數組分為已排序和未排序兩部分
  2. 從未排序部分取出一個元素
  3. 在已排序部分找到適當的位置插入
  4. 重複步驟2-3，直到所有元素都排序完成

時間複雜度分析：

  1. 最壞情況(Worst Case): O(n²)
    • 當數組完全逆序時
    • 每個元素都需要移到最前面
    • 比較和移動次數最多
  2. 最好情況(Best Case): O(n)
    • 當數組已經排序時
    • 每個元素只需要比較一次
    • 不需要移動元素
  3. 平均情況(Average Case): O(n²)
    • 對於隨機排列的數組
    • 平均需要移動和比較 n²/4 次

空間複雜度：

  • O(1)，只需要一個臨時變量存儲 key
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void InsertionSort(int[] arr)
{
    int n = arr.Length;

    // 從第二個元素開始，因為第一個元素可以視為已排序
    for (int i = 1; i < n; i++)
    {
        // 保存當前要插入的元素
        int key = arr[i];
        
        // j 用於在已排序部分從後向前比較
        int j = i - 1;

        // 將比 key 大的元素都向後移動一位
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        // 找到合適的位置，插入 key
        arr[j + 1] = key;
    }
}