算法基础

插入排序是一种非常简单，稳定的就地排序算法。它在小序列上表现良好，但在大型列表上效率低得多。在每一步中，算法都会考虑给定序列的第 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]