Insertion Sort 視覺化

輸入區

尚未開始

統計

演算法說明

插入排序從第二個元素開始，將每個元素插入到左側已排序區間的正確位置，保持左側始終有序。

偽代碼：

INSERTION-SORT(A)
  for i = 2 to n
    key = A[i]
    j = i - 1
    while j >= 1 and A[j] > key
      A[j+1] = A[j]
      j = j - 1
    A[j+1] = key

複雜度：最好 O(n)、平均/最壞 O(n²)、空間 O(1)

優點：穩定、適合近乎有序資料、實作簡單；缺點：隨機大資料效率不佳。