输入：n个数的一个序列
输出：输入序列的一个排列，满足 a1 ≤ a2 ≤ ... ≤ an。
对于插入排序，我们将其伪代码命名为Insertion-sort，其中的参数是一个数组A[1..n]，包含长度为n的要排序的一个序列。（在代码中，A中元素的数目n用A.length来表示。）该算法原址排序输入的数：算法在数组A中重排这些数，在任何时候，最多只有其中的常数个数字存储在数组外面。在过程Insertion-sort结束时，输入数组A包含排序好的输出序列。
Insertion-sort(A)
for (j = 2; j <= A.length; j++)
key = A[j]
// Insert A[j] into the sorted sequence A[1..j-1]
i = j - 1
while (i > 0 && A[i] > key)
A[i+1] = A[i]
i = i - 1
A[i+1] = key
