🧩 插入排序法演示

操作原理

  1. 把陣列想成「左邊已排序，右邊未排序」。
  2. 每次從未排序區取出一個元素（key）。
  3. 將 key 與左邊已排序元素由右往左比較，找到正確插入位置。
  4. 比 key 大的元素向右移動一格，最後把 key 插入空位。

操作過程步驟

  1. 從 i = 1 開始，令 key = array[i]。
  2. 設 j = i - 1，向左比較 array[j] 與 key。
  3. 若 array[j] > key，將 array[j] 右移到 array[j + 1]，j 持續左移。
  4. 直到 j < 0 或 array[j] <= key 為止。
  5. 把 key 放到 array[j + 1]，完成一輪插入。
  6. i 往右移動，重複到陣列尾端。

時間複雜度分析

最壞情況：O(n²)
當陣列為逆序時，每次插入都要一路比較與搬移到最前面
平均情況：O(n²)
隨機資料下，平均每輪仍需搬移一定數量元素
最佳情況：O(n)
當陣列已排序時，每輪只需一次比較就可完成插入
空間複雜度：O(1)
原地排序，額外只使用少量變數（key、j）

視覺化演示

按下「開始排序」觀察 key 如何插入左側已排序區
已排序區
當前 key
比較中
右移中
比較次數: 0
搬移次數: 0