插入排序

插入排序可以在原数组之上进行操作，不需要分配新的数组存储排序结果。基本策略是从数组中的第二个元素开始，把左边的所有元素作为已排序元素，而右边的元素是等待排序的元素。

首先指定一个等待排序的元素，然后循环左侧的每个元素，如果比当前等待排序的元素大，就把它右移一格，否则把当前待排序元素插入当前被循环元素的右边。

以下是ruby代码：

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

j = 1
while j < a.length do
    key = a[j]
    i = j - 1
    while i >= 0 && a[i] > key do
        a[i + 1] = a[i]
        i = i - 1
    end
    a[i + 1] = key
    j = j + 1
end

puts a