算法流程：
将第i个元素插入其左边（或右边）的有序元素中。对于第i个元素，其左边的元素a[0], a[1], a[2], ... a[i-1]是有序的。
从第2个元素（即i=1）开始，直到最后一个元素，依次进行如下过程：
a[i]与a[i-1]比较，若a[i]<a[i-1]则交换a[i]与a[i-1]；
a[i-1]与a[i-2]比较，若a[i-1]<a[i-2]则交换a[i-1]与a[i-2]；
直到不满足a[k]<a[k-1]或进行到最后一组元素a[1]与a[0]
示例如下：
实现代码：
public static void insertionSort(int[] a) {
int N = a.length;
int temp;
for (int i=1; i<N; i++) {
for (int j=i; j>0 && a[j]<a[j-1]; j--) {
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
算法复杂度：
若数组的某些部分是有序的，插入排序对这样的数组很有效。
倒置指的是数组中两个顺序颠倒的元素。如E X A M P L E中，共有E-A、X-A、X-M、X-P、X-L、X-E、M-L
M-E、P-L、P-E、L-E 11对倒置。
倒置数与排序中的交换数是相同的。对于上述数组中的元素M与其左边的元素只有倒置X-M，又由于左边的元素是有序的故只需要交换一次，及X-M。
同理，元素E与其左边的元素的倒置有X-E、M-E、P-E、L-E，故需要交换4次。
算法稳定性：
插入排序是稳定的。
其他性质：
与选择排序相比：
