演算法基礎

插入排序是一種非常簡單,穩定的就地排序演算法。它在小序列上表現良好,但在大型列表上效率低得多。在每一步中,演算法都會考慮給定序列的第 i 個元素,將其向左移動直到它處於正確的位置。

圖形化的插圖

http://i.stack.imgur.com/Jn79T.jpg

虛擬碼

for j = 1 to length(A)
    n = A[j]
    i = j - 1
    while j > 0 and A[i] > n
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = n

考慮以下整數列表:

[5, 2, 4, 6, 1, 3]

該演算法將執行以下步驟:

  1. [5, 2, 4, 6, 1, 3]
  2. [2, 5, 4, 6, 1, 3]
  3. [2, 4, 5, 6, 1, 3]
  4. [2, 4, 5, 6, 1, 3]
  5. [1, 2, 4, 5, 6, 3]
  6. [1, 2, 3, 4, 5, 6]