直接插入排序（Straight Insertion Sort)是一种最简单的排序方法
最好时间： O(n)
平均时间： O(n^2)
最差时间： O(n^2)
辅助缓存： O(1)
稳定性： 稳定
备注：大部分已经有序时较好
基本操作： 将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序表
先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序为止
Java实现如下：
//升序排列
public class TestSort {
public static void insertSort(int[] a) {
if (a!=null) {
for(int i=1; i<a.length; i++){
int temp = a[i];
int j=i;
//给要插入的元素找到合适的位置
if(a[j-1]>temp){
while (j>=1&&a[j-1]>temp){
a[j] = a[j-1];
j--;
}
}
a[j] = temp;
}
}
}
public static void main(String[] args){
int array = {7, 3, 19, 40, 4 , 7};
insertSort(array);
}
}