演算法基礎

插入排序是一種非常簡單，穩定的就地排序演算法。它在小序列上表現良好，但在大型列表上效率低得多。在每一步中，演算法都會考慮給定序列的第 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]